问为什么Java6 Arrays#sort(Object[])在小数组中从合并排序改为插入排序？

EN

是的，这是故意的。虽然mergesort的Big-O比插入排序等二次排序的大O小，但它所做的操作更复杂，因此速度更慢。

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

另一方面，插入排序本质上很简单，并且使用关于8^2=64的操作要快得多。

这样想吧。当您手动对包含10个数字的列表进行排序时，是否使用合并排序？不，因为你的大脑更擅长做简单的事情，比如插入排序。但是，如果我给您一年时间对包含100,000个数字的列表进行排序，您可能会更倾向于对其进行合并排序。

至于魔术数7，根据经验得出它是最优的。

编辑:在8个元素的标准插入排序中，最坏的情况会导致大约36次比较。在规范的合并排序中，您有大约24次比较。再加上方法调用的开销和操作的复杂性，插入排序应该更快。此外，如果您查看平均情况，插入排序进行的比较比36要少得多。

插入排序为n(n-1)/2，合并排序为n*(以2为底的对数n)。

考虑到这点-

长度为5的数组的

1. =>分段排序= 10，合并排序为11.609
2. 长度为6 =>分段排序= 15，合并排序为15.509
3. 长度为7的数组=>分段排序= 21，合并排序为19.651
4. 长度为8的=>分段排序= 28，合并排序为24

<代码>G211

从上面的数据可以看出，在长度为6之前，分段排序速度更快，在长度为7之后，合并排序是有效的。

这就解释了为什么使用7。

我的理解是，这是一个经验派生的值，其中插入排序所需的时间实际上较低，尽管(可能)需要更多的比较。这是因为在合并排序接近尾声时，数据可能几乎已排序，这使得插入排序执行得很好。