java - Java 7 是否对方法 Arrays.Sort 使用 Tim Sort？

Question

我找不到Java 7 的文档，我只能找到关于Java 6 的，它仍然是快速或合并。有谁知道如何在 Java 7 中找到方法 Arrays.sort 的文档？

Answer 1

Java 7 对基元使用 Dual-Pivot Quicksort，对对象使用 TimSort。

根据Java 7 API doc for primitives:

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

根据Java 7 API doc for objects:

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techiques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

Timsort是一种混合的“合并排序和插入排序”。

不确定这是否与 Java 6 中的有很大不同，for Arrays.sort JDK6:

a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993)

对于 Object[] 或集合 (Collections.sort()) 使用合并排序。