Is Java 7 using Tim Sort for the Method Arrays.Sort?
I can't find the documentation of Java 7, I can 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 in Java 7?
Answer
Java 7 uses Dual-Pivot Quicksort for primitives and TimSort for objects.
According to the 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.
According to the 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 is a hybrid "merge sort and insertion sort."
Not sure if this is much different from what it was in 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)
For Object[] or collections (Collections.sort()) merge sort is used.