algorithm - 归并排序为什么要在阈值交叉后使用插入排序

Question

我到处都读到对于分而治之的排序算法，如 Merge-Sort 和 Quicksort，与其递归直到只剩下一个元素，不如当达到某个阈值(比如 30 个元素)时，转向 Insertion-Sort。这很好，但为什么只有 Insertion-Sort？为什么不用 Bubble-Sort 或 Selection-Sort，它们都具有相似的 O(N^2) 性能？ Insertion-Sort 应该只有在许多元素被预排序时才会派上用场(虽然 Bubble-Sort 也应该有这个优势)，但除此之外，为什么它会更高效比其他两个？

其次，在 this link ，在第二个答案及其附带的评论中，它说 O(N log N) 与 O(N^2) 相比表现不佳直到某个 N 。怎么会？ N^2 的性能应该总是比 N log N 差，因为 N > log N 对于所有 N >= 2，对吗？

Answer 1

如果您在达到阈值时退出分而治之的快速排序的每个分支，您的数据将如下所示:

[the least 30-ish elements, not in order] [the next 30-ish ] ... [last 30-ish]

插入排序有一个相当令人愉快的特性，你可以在整个数组上只调用它一次，它的性能基本上与你对每个 30 block 调用一次它的性能相同。所以不要在你的循环中调用它，您可以选择最后调用它。这可能不会更快，尤其是因为它通过缓存提取整个数据需要额外的时间，但取决于代码的结构，它可能很方便。

冒泡排序和选择排序都没有这个属性，所以我认为答案可能很简单就是“方便”。如果有人怀疑选择排序可能更好，那么他们就有责任“证明”它更快。

请注意，这种插入排序的使用也有一个缺点——如果您这样做并且分区代码中存在错误，那么只要它不会丢失任何元素，只是错误地分区它们，您将 从不注意。

编辑:显然，此修改是由 Sedgewick 完成的，他在 1975 年获得了有关 QuickSort 的博士学位。最近由 Musser(Introsort 的发明者)对其进行了分析。引用 https://en.wikipedia.org/wiki/Introsort

Musser also considered the effect on caches of Sedgewick's delayed small sorting, where small ranges are sorted at the end in a single pass of insertion sort. He reported that it could double the number of cache misses, but that its performance with double-ended queues was significantly better and should be retained for template libraries, in part because the gain in other cases from doing the sorts immediately was not great.

无论如何，我不认为一般的建议是“无论你做什么，都不要使用选择排序”。建议是，“对于非常小的输入，插入排序优于快速排序”，当您实现快速排序时，这很容易向您自己证明。如果你想出另一种在相同的小数组上明显优于插入排序的排序，那么这些学术资源都不会告诉你不要使用它。我想令人惊讶的是，建议始终针对插入排序，而不是每个来源都选择自己喜欢的(介绍老师坦率地惊人喜欢冒泡排序——我不介意我从不又听说了)。插入排序通常被认为是小数据的“正确答案”。问题不在于它是否“应该”快，而在于它是否确实如此，而且我从来没有特别注意到任何基准消除了这个想法。

寻找此类数据的一个地方是 Timsort 的开发和采用。我很确定 Tim Peters 选择插入是有原因的:他没有提供一般性建议，他正在优化一个库以供实际使用。