java - 为什么 Collections.sort 使用 Mergesort 而 Arrays.sort 不使用？

Question

我正在使用 JDK-8 (x64)。对于 Arrays.sort (原语)，我在 Java 文档中找到了以下内容:

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch.`

对于 Collections.sort(对象)我发现了这个“Timsort”:

This implementation is a stable, adaptive, iterative mergesort ... This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array.

如果 Collections.sort 使用数组，为什么不直接调用 Arrays.sort 或使用双轴 QuickSort？为什么要使用合并排序？

Answer 1

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

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

---

¹Quicksort 的效率优势就地完成时需要更少的内存。但它有一个戏剧性的最坏情况性能，不能利用数组中预排序数据的运行，TimSort可以。

因此，排序算法从一个版本到另一个版本都进行了重新设计，同时保留在现在具有误导性的类 DualPivotQuicksort 中。此外，文档没有跟上，这表明，在没有必要的情况下，在规范中命名内部使用的算法通常是一个坏主意。

目前情况(包括Java 8到Java 11)如下:

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