Menu
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?
413
Go uses insertion sort and stable minimum storage merging for stable sorts. Java uses dual-pivot sort for primitives, which is an unstable sort. Java uses timsort, a stable sorting algorithm for objects.
As mentioned in the official JavaDoc, Arrays. sort uses dual-pivot Quicksort on primitives. It offers O(n log(n)) performance and is typically faster than traditional (one-pivot) Quicksort implementations.
TimSort is a highly optimized mergesort, it is stable and faster than old mergesort. when comparing with quicksort, it has two advantages: It is unbelievably fast for nearly sorted data sequence (including reverse sorted data); The worst case is still O(N*LOG(N)).
When the array is almost sorted, insertion sort can be preferred. When order of input is not known, merge sort is preferred as it has worst case time complexity of nlogn and it is stable as well. When the array is sorted, insertion and bubble sort gives complexity of n but quick sort gives complexity of n^2.
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.
138
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
