问为什么在合并排序中应该在阈值交叉之后使用插入排序

EN

在实践中，

1. 插入排序至少比冒泡排序快。它们的渐近运行时间是相同的，但插入排序具有更好的常量(每次迭代操作更少/更便宜)。最值得注意的是，它只需要线性数量的元素对交换，并且在每个内循环中，它执行n/2个元素中的每个元素与可以存储在寄存器中的“固定”元素之间的比较(而冒泡排序必须从内存中读取值)。例如，插入排序在其内部循环中比冒泡排序做的工作更少。
2. 答案声称，对于“合理”n，10000 n lg n> 10 n²。这在大约14000个元素中是正确的。

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

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

插入排序有一个令人愉悦的特性，你可以在整个数组上只调用它一次，而且它的执行基本上与你对每30个块调用一次的效果相同。因此，您可以选择最后调用它，而不是在循环中调用它。这可能不会更快，特别是因为它需要额外的时间从缓存中提取整个数据，但根据代码的结构，这可能会很方便。

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

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

编辑:显然，这个修改是由Sedgewick完成的，他于1975年在QuickSort上写了他的PhD。最近，Musser (Introsort的发明者)对其进行了分析。参考https://en.wikipedia.org/wiki/Introsort

Musser还考虑了Sedgewick的延迟小排序对缓存的影响，在Sedgewick的延迟小排序中，小范围在插入排序的一次传递中在末尾排序。他报告说，它可以将缓存未命中的数量增加一倍，但它在双端队列中的性能要好得多，应该为模板库保留下来，部分原因是在其他情况下，立即进行排序的收益并不大。

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

寻找这些数据的一个地方是Timsort的开发和采用。我很确定Tim Peters选择插入是有原因的:他不是在提供一般的建议，他是在优化一个真正有用的库。

我很惊讶没有人提到一个简单的事实，即插入排序对于“几乎”排序的数据来说要快得多。这就是它被使用的原因。