I can't find the documentation of Java 7, I only find about the Java 6, which is still quick or merge. Does anyone know how to find the documentation of the method Arrays.Sort of Java 7? Thank you.
+4
A:
Java 7 uses Dual-Pivot Quicksort for primitives and TimSort for objects.
According to the Java 7 draft 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.
According to the Java 7 draft 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.
Not sure if this is much different from what it was in Java 6:
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)
Michael Borgwardt
2010-10-25 20:01:57
ah great. Thanks.For primitives, it use dual pivot quick sort, and for object, it uses Tim Sort
Osvaldo
2010-10-25 20:05:18
Any idea why the distinction is made between timsort for objects and dual pivot quicksort for primitives? Memory considerations maybe?
mR_fr0g
2010-10-25 21:54:40
@mR_fr0g: see my answer in this thread: http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types/3707236#3707236
Michael Borgwardt
2010-10-26 04:15:06
+1
A:
Yes, Java 7 will use Timsort for Arrays.sort. Here is the commit http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79