为什么Java 6 Arrays＃sort（Object ）从mergesort更改为insertionsort用于小数组？

如果数组长度小于某个阈值，则Arrays.java Java 6的mergesort实现使用Arrays.java -sort。此值被硬编码为7.由于算法是递归的，因此对于大型数组，这最终会发生多次。规范的合并排序算法不会这样做，只需使用merge-sort，直到列表中只有1个元素。

这是优化吗？如果是这样，它应该如何帮助？为什么7 ？插入排序（甚至<=7件事）会大大增加对大型数组进行排序所需的比较次数 – 因此会增加compareTo()调用速度慢的排序成本。

对于INSERTIONSORT_THRESHOLD的不同值，array-size vs＃-of-comparisons

（x轴是size of array ，y轴是# of comparisons ，对于不同的INSERTIONSORT_THRESHOLD值）

是的，这是故意的。虽然mergesort的Big-O小于插值排序等二次排序，但它的操作更复杂，因此更慢。

考虑对长度为8的数组进行排序。除7次合并操作外，合并排序还会对自身进行~14次递归调用。每个递归调用都会给运行时带来一些非平凡的开销。每个合并操作都涉及一个循环，其中必须初始化，递增和比较索引变量，必须复制临时数组等等。总而言之，您可以期待超过300个“简单”操作。

另一方面，插入排序本质上很简单，使用大约8 ^ 2 = 64次操作，这要快得多。

这样想吧。当您手动对10个数字列表进行排序时，是否使用合并排序？不，因为你的大脑在做插入排序之类的简单事情方面要好得多。但是，如果我给你一年的时间来排序100,000个数字的列表，你可能更倾向于合并它。

对于幻数7，根据经验推导出最佳。

编辑：在8个元素的标准插入类型中，最坏的情况导致~36个比较。在规范合并排序中，您进行了~24次比较。添加方法调用的开销和操作的复杂性，插入排序应该更快。另外，如果你看一下平均情况，插入排序会比36更少的比较。

插入排序为n（n-1）/ 2，合并排序为n *（log n与基数2）。

考虑到这一点 –

从上面的数据可以清楚地看出，直到长度为6，排版分类更快，在7之后，合并排序是有效的。

这解释了为什么使用7。

我的理解是，这是一个经验导出的值，其中插入排序所需的时间实际上较低，尽管需要（可能）更高的比较次数。这是因为在mergesort的末尾附近，数据可能几乎被排序 ，这使得插入排序表现良好。