为什么Collections.sort使用Mergesort但Arrays.sort不使用？

Question

我正在使用JDK-8（x64）。对于Arrays.sort（原始），我在Java文档中发现了以下内容：

排序算法是Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch编写的Dual-Pivot
Quicksort 。

对于Collections.sort（对象），我找到了“ Timsort”：

此实现是一个稳定的，自适应的，迭代的 mergesort 。此实现 将指定的列表转储到数组中，对数组进行排序
，然后遍历列表，从数组中的相应位置重置每个元素。

如果Collections.sort使用数组，为什么不调用Arrays.sort或使用 双轴QuickSort ？为什么要使用
Mergesort ？

Answer 1

该API保证了Quicksort不提供的 稳定 排序。但是，当按
原始值 的自然顺序对 原始值
进行排序时，您不会注意到差异，因为原始值没有身份。因此，Quicksort可以用于原始数组，并在认为效率更高时使用¹。
__

对于对象，您可能会注意到，当具有不同标识的对象根据其equals实现或提供的内容被视为相等时，将Comparator更改其顺序。因此，Quicksort不是一个选择。所以一个变种归并时，当前的Java版本使用
TimSort
。这适用于Arrays.sort和Collections.sort，尽管使用Java 8，它List本身也可以覆盖排序算法。

¹的效率优势快速排序就地完成时，需要较少的内存。但是，它在最坏的情况下具有惊人的性能，无法利用数组中的预排序数据运行，而TimSort可以做到。

因此，排序算法在版本之间进行了重新设计，同时保留在现在具有误导性的class中DualPivotQuicksort。同样，文档也没有赶上，这表明，在不必要的情况下，在规范中命名内部使用的算法通常是个坏主意。

当前情况（包括Java 8到Java 11）如下：

• 通常，原始数组的排序方法仅在某些情况下才使用Quicksort。对于较大的阵列，它们将尝试像TimSort一样首先识别经过预排序的数据，并在运行次数未超过特定阈值时将其合并。否则，它们将退回到Quicksort，但实现方式将退回到小范围的插入排序，这不仅会影响小数组，还会影响快速排序的递归。
• sort(char[],…)并sort(short[],…)添加另一种特殊情况，对长度超过特定阈值的数组使用计数排序
• 同样，sort(byte[],…)将使用Counting sort，但阈值要小得多，这与文档形成了最大的对比，因为sort(byte[],…)从未使用Quicksort。它仅对小数组使用插入排序，否则对计数排序使用。