Java 6 的 mergesort 实现在数组长度小于某个阈值时使用插入排序。此值硬编码为 7。由于该算法是递归的，因此对于大型数组，这种情况最终会发生很多次。规范的合并排序算法不会这样做，只是一直使用合并排序，直到列表中只有 1 个元素。Arrays.java
这是优化吗？如果是这样，它应该如何帮助？为什么？插入排序（甚至是事物）大大增加了对大型数组进行排序所需的比较次数 - 因此会增加调用缓慢排序的成本。7<=7compareTo()
（x 轴为 ，y 轴为 ，适用于size of array# of comparisonsINSERTIONSORT_THRESHOLD)
是的，这是故意的。虽然合并排序的 Big-O 小于二次排序（如插入排序）的 Big-O，但它执行的操作更复杂，因此速度更慢。
考虑对长度为 8 的数组进行排序。除了 7 个合并操作之外，合并排序还会对自身进行大约 14 次递归调用。每个递归调用都会给运行时带来一些不小的开销。每个合并操作都涉及一个循环，其中索引变量必须初始化、递增和比较，临时数组必须复制等。总而言之，您可以期待超过300种“简单”操作。
另一方面，插入排序本质上是简单的，使用大约8 ^ 2 = 64个操作，这要快得多。
这样想吧。当您手动对包含10个数字的列表进行排序时，是否使用合并排序？不，因为你的大脑更擅长做简单的事情，比如插入排序。但是，如果我给你一年的时间来对100，000个数字的列表进行排序，你可能更倾向于合并排序它。
至于幻数7，根据经验推导它是最优的。
编辑：在8个元素的标准插入类型中，最坏的情况会导致大约36个比较。在规范合并排序中，您有大约 24 个比较。加上方法调用的开销和操作的复杂性，插入排序应该更快。此外，如果您查看平均情况，插入排序的比较次数将远远少于36。
插入排序为 n（n-1）/2，合并排序为 n*（以 2 为基数的 log n）。
考虑到这一点 -
从上面的数据可以清楚地看出，直到长度6，插入排序更快，7之后，合并排序是有效的。
这就解释了为什么使用7。
