我正在查看grepcode上java.util.ArrayList的sort()方法的源代码。他们似乎对小数组（大小 < 7）使用插入排序，对大数组使用合并排序。我只是想知道这是否会产生很大的不同，因为它们仅对大小 < 7 的数组使用插入排序。在现代机器上几乎不会注意到运行时间的差异。
我在科门读过这个：
尽管合并排序在 O(n*logn) 最坏情况下运行，而插入排序在 O(n*n) 最坏情况下运行，插入排序中的常数因子可以使其在实践中更快地处理许多机器上的小问题. 因此，当子问题变得足够小时，通过在合并排序中使用插入排序来粗化递归的叶子是有意义的。
如果我会为我需要的某些组件设计排序算法，那么我会考虑在运行时间的差异（与合并排序相比）变得明显之前使用插入排序来获得更大的大小（可能高达大小 < 100）。
我的问题是达到尺寸 < 7 的分析是什么？
在现代机器上，运行时间的差异几乎不会被注意到。
当您意识到整体排序算法是递归的并且小数组排序实际上是该递归的基本情况时，对小数组进行排序需要多长时间变得非常重要。
我没有任何关于七号是如何被选中的内幕消息。但是，如果没有在小型阵列上对竞争算法进行基准测试，并据此选择最佳算法和阈值，我会感到非常惊讶。
PS 值得指出的是，Java7 默认使用Timsort。
我为将来访问此线程并记录我自己的研究的人发布此信息。在寻找选择 7 之谜的答案时，我偶然发现了这个极好的链接：
您应该阅读标题为“计算 minrun”的部分。
给出一个要点， minrun 是算法应该开始使用插入排序的数组的截断大小。因此，我们将始终拥有大小为“minrun”的排序数组，我们需要在其上运行合并操作来对整个数组进行排序。
在 java.util.ArrayList.sort() 中，“minrun”被选择为 7，但就我对上述文档的理解而言，它打破了这个神话并表明它应该接近 2 的幂且小于 256以及超过 8 个。从文件中引用：
在 256 处，二进制插入排序中的数据移动成本明显受到影响，而在 8 处，函数调用次数的增加明显受到损害。选择2的幂在这里很重要，这样合并最终会完美平衡（请参阅下一节）。
我要说的一点是，“minrun”可以是小于 64 的 2 的任何幂（或接近 2 的幂），而不会影响 TimSort 的性能。
http://en.wikipedia.org/wiki/Timsort
“Timsort 是一种混合排序算法，源自归并排序和插入排序，旨在在多种现实世界数据上表现良好......该算法找到已经排序的数据子集，并使用子集对数据更有效。这是通过将已识别的子集（称为运行）与现有运行合并来完成的，直到满足某些标准。
关于7号：
“...此外，可以看出，只有当初始元素不是另一次运行的前七个元素之一时，疾驰才是有益的。这也导致 MIN_GALLOP 设置为 7。为了避免疾驰模式的缺点，合并函数调整min-gallop的值，如果元素来自当前考虑的数组（即连续返回元素一段时间的数组），则min-gallop的值减1，否则, 值加 1, 因此不鼓励返回到驰骋模式. 当这样做时, 在随机数据的情况下, min-gallop 的值变得如此之大, 以至于返回到驰骋模式永远不会发生.
在使用merge-hi的情况下（即从右到左进行合并），驰骋需要从数据的右端开始，也就是最后一个元素。从头开始驰骋也给出了所需的结果，但进行了比所需更多的比较。因此，驰骋的算法包括使用一个变量，该变量给出了驰骋应该开始的索引。因此，该算法可以在任何索引处进入疾驰模式并继续如上所述，如在下一个索引处检查，该索引偏移了 1, 3, 7,...., (2k - 1).. 和依此类推，从当前索引开始。在 merge-hi 的情况下，索引的偏移量将是 -1、-3、-7、...."