algorithm - 部分排序序列的最佳排序算法？

Question

我必须回答以下问题:

如果第n-m部分推荐什么排序算法
已经排序而剩余部分 m 未排序？是否有任何算法可以进行 O(n log m) 比较？ O(m log n) 比较怎么样？

我只是找不到解决方案。

我的第一个想法是插入排序，因为 O(n) 对于几乎已排序的序列。但是由于我们不知道 m 的大小，即使序列已经排序一半，运行时很可能是 O(n^2) 不是吗？

然后我认为它可能是快速排序，因为它需要(从 k=1 到 n 的总和)Cavg (1-m) + Cavg (n-m) 比较。但是在忽略序列的 n-m 部分后，剩余的序列在快速排序中是 1-m 而不是 m。

合并排序和堆排序应该有 O(m log m) 的运行时间，我会说剩下的序列 m。

有没有人有想法或可以给我一些建议？

问候

Answer 1

您是否尝试过以 O(m log (m)) 复杂度单独排序剩余部分 m(使用任何您喜欢的算法:MergeSort , HeapSort, QuickSort, ...)，然后使用 MergeSort 将该部分与已排序的部分合并 (您甚至不需要完全实现 MergeSort - 只需单次传递它的内部循环体即可合并两个已排序的序列)？

这将导致 O(m*log(m) + n + m) = O(m*log(m) + n) 复杂度。我认为不可能在单核 CPU 上找到更好的渐近复杂度。尽管合并结果数组需要额外的 O(n+m) 内存。