为什么java使用合并排序来排序大于元素7的数组

Question

根据维基百科:

"在Java中,Arrays.sort()方法根据数据类型使用合并排序或调整快速排序,并且当正在排序的数组元素少于7个时,实现效率切换到插入排序"

但为什么？合并排序和快速排序都是O(n log n).

Answer 1

算法不同的地方是它们的典型案例行为,这就是插入排序是最糟糕的情况之一.在另一方面,对于非常小的集合(N≈ñ ²)插入排序的简单胜.

Java的算法选择规则首先选择QuickSort,并且由于特定的限制而仅返回其他内容.QuickSort,即,是一种不稳定的排序,因此仅适用于基元的排序.对于参考类型,TimSort用于OpenJDK 7(以前的MergeSort).

Answer 2

这不是特别的：

Arrays.java 的排序方法对基元数组使用快速排序，对对象数组使用合并排序。

为什么Java的Arrays.sort方法对不同的类型使用两种不同的排序算法？

另外，根据文档：

例如，sort(Object[]) 使用的算法不必是归并排序，但它必须是稳定的。

javadoc 中的另一句话：

这种排序保证是稳定的：相同的元素不会因排序而重新排序。

实现说明：此实现是一种稳定、自适应、迭代的归并排序，当输入数组部分排序时，需要的比较次数远少于 n lg(n)，而当输入数组随机排序时，它提供传统归并排序的性能。如果输入数组接近排序，则实现需要大约 n 次比较。临时存储要求各不相同，从几乎排序的输入数组的小常量到随机排序的输入数组的 n/2 对象引用。

该实现在其输入数组中同等地利用升序和降序，并且可以在同一输入数组的不同部分中利用升序和降序。它非常适合合并两个或多个已排序的数组：只需连接数组并对结果数组进行排序即可。

该实现改编自 Tim Peters 的 Python 列表排序 (TimSort)。