我正在查看 grepcode 上 java.util.ArrayList 的 sort（） 方法的源代码。他们似乎对小数组（大小< 7）使用插入排序，对大型数组使用合并排序。我只是想知道这是否会产生很大的不同，因为它们仅对大小为7的数组使用插入排序<。运行时间的差异在现代机器上几乎不明显。
我在Cormen中读到过这个：
尽管合并排序在 O（n*logn） 最坏情况时间运行，插入排序在 O（n*n） 最坏情况时间运行，但插入排序中的常数因素可以使其在实践中更快，因为许多计算机上的小问题大小。因此，当子问题变得足够小时，通过在合并排序中使用插入排序来粗化递归的叶子是有意义的。
如果我为我需要的某些组件设计了排序算法，那么我会考虑在运行时间的差异与合并排序相比变得明显之前，对更大的大小（可能最大为 <100）使用插入排序。
我的问题是，得出<7号尺寸背后的分析是什么？
运行时间的差异在现代机器上几乎不明显。
当您意识到整个排序算法是递归的时，对小数组进行排序所需的时间变得非常重要，而小数组排序实际上是该递归的基本情况。
我没有任何关于数字七是如何被选中的内幕信息。但是，如果不是因为对小阵列上的竞争算法进行基准测试，并基于此选择最佳算法和阈值，我会感到非常惊讶。
附言：值得指出的是，Java7默认使用Timsort。
我正在为将来访问此线程并记录我自己的研究的人发布此内容。我偶然发现了这个优秀的链接，以寻找选择7的奥秘的答案：
您应该阅读标题为“计算最小值”的部分。
为了给出一个要点，minrun是数组的截止大小，低于该大小，算法应开始使用插入排序。因此，我们将始终拥有大小为“minrun”的排序数组，我们需要在其上运行合并操作来对整个数组进行排序。
在java.util.ArrayList.sort（）中，“minrun”被选为7，但就我对上述文档的理解而言，它打破了这个神话，并表明它应该接近2的幂，小于256和大于8。引用该文件：
在256时，二进制插入排序中的数据移动成本显然会受到损害，而在8时，函数调用次数的增加显然会受到损害。在这里选择一些2的幂很重要，这样合并最终才能完全平衡（请参阅下一节）。
我要说的是，“最小值”可以是小于64的2次幂（或接近2的幂）的任何次幂，而不会妨碍TimSort的性能。
