我必须开发一种能够对 n 元素列表进行排序的算法，其中对第一个 (n-root(n)) 元素进行排序。是的，这是一个家庭作业问题。
经过对互联网和stack-overflow的一些研究，我相信插入排序和冒泡排序最适合部分排序的数组。该链接清楚地表明插入排序优于合并排序。我已经把插入排序作为我作业的答案。
但是，当我开始进行渐近复杂性分析时，我会感到困惑。
对于插入排序，我们至少要看看每个元素。如果元素未排序，我们将不得不进行移位/反转。因此，插入排序将有 O(n + m)，其中 m 是总反转。或者，我们也可以说它具有线性复杂度 O(n)。
对于归并排序，我们需要对未排序的 root(n) 元素进行归并排序，这将给出 root(n)log(root (n)) 复杂度。此外，我们需要与排序列表进行合并（这将花费 O(n)）。因此，复杂度将是 O(root(n) log (root (n)) + n) 或 O(n)，因为 n 支配 root(n) log (root(n))。
为什么两者具有相同的渐近复杂度？这只是我的好奇心。我可能在复杂性计算中间的某个地方犯了错误。
我是学生，还在学习。我很感激任何帮助。谢谢。