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

我到处都读到了分而治之的排序算法，例如Merge-Sort and Quicksort，与其递归直到只剩下一个元素，不如转移到Insertion-Sort当达到某个阈值（例如 30 个元素）时。这很好，但为什么只是Insertion-Sort？为什么不Bubble-Sort or Selection-Sort，两者都有类似的O(N^2)表现？Insertion-Sort仅当许多元素被预先排序时才应该派上用场（尽管这种优势也应该伴随Bubble-Sort），但除此之外，为什么它比其他两个更有效呢？

其次，在这个链接，在第二个答案及其附带的评论中，它说O(N log N)与相比表现不佳O(N^2)达到一定的N。怎么会？N^2应该总是表现得比N log N, since N > log N对于所有 N >= 2，对吗？

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

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

插入排序有一个相当令人愉快的属性，您可以在整个数组上调用它一次，并且它的执行效果与您为每个 30 的块调用一次它的执行效果基本相同。因此，您不必在循环中调用它，而是可以最后调用它的选项。这可能不是faster，特别是因为它会额外通过缓存提取整个数据，但根据代码的结构，它可能会很方便。

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

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

编辑：显然这个修改是由 Sedgewick 完成的，他于 1975 年撰写了有关 QuickSort 的博士学位。Musser（Introsort 的发明者）最近对其进行了分析。参考https://en.wikipedia.org/wiki/Introsort

Musser 还考虑了 Sedgewick 延迟对缓存的影响 小排序，其中小范围在单个末尾排序 插入排序的传递。他报告说，这可以使数量增加一倍。 缓存未命中，但其双端队列的性能是 明显更好，应该保留模板库，在 部分原因是在其他情况下立即进行排序会带来好处 不太好。

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

寻找此类数据的一个地方是 Timsort 的开发和采用。我很确定蒂姆·彼得斯选择了插入因为某种原因：他没有提供一般性建议，他正在优化一个库以供实际使用。