algorithm - 在部分排序的数组中，插入比归并排序有何优势？

Question

我必须开发一种能够对 n 元素列表进行排序的算法，其中第一个 (n- root(n)) 个元素已排序。是的，这是一道作业题。

经过一些research在互联网上和stack-overflow ，我相信插入排序和冒泡排序最适合部分排序的数组。这link清楚地表明插入排序优于归并排序。我把插入排序作为我作业的答案。

但是，当我开始进行渐近复杂度分析时，我会感到困惑。

对于插入排序，我们至少要看一下每个元素。如果元素未排序，我们将不得不进行移位/反转。因此，插入排序的复杂度为 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))。

为什么两者具有相同的渐近复杂度？这只是我的好奇心。我可能在复杂性计算过程中的某个地方犯了错误。

我是一名学生，还在学习中。我感谢任何帮助。谢谢。

Answer 1

此列表中的总反转计数可能高达 (n - Sqrt(n)) * Sqrt(n) = O(n^3/2)。

示例:100 个元素的列表 (10 11 12..99 100 1 2 3 4 5 6 7 8 9 10) 的倒置计数为 900，因此插入排序将执行大约 900 次操作(每个尾部元素移动 90 次)