According to Wikipedia:
"In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted"
But why? Both merge sort and quick sort are O(n log n).
Where the algorithms differ is their typical case behavior and this is where insertion sort is one of the worst. On the other hand, for very small collections (n ≈ n2) insertion sort's simplicity wins.
Java's algorithm selection rules prefer QuickSort first, and only fall back to something else due to specific restrictions. QuickSort, namely, is an unstable sort and thus is only acceptable for the sorting of primitives. For reference types, TimSort is used as of OpenJDK 7 (previously MergeSort).
n^2 < 10n for n < 10.
It's not that ad-hoc:
Arrays.java's sort method uses quicksort for arrays of primitives and merge sort for arrays of objects.
Why does Java's Arrays.sort method use two different sorting algorithms for different types?
Also, according to the docs:
For example, the algorithm used by sort(Object[]) does not have to be a mergesort, but it does have to be stable.
And another quote from the javadoc:
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.
The implementation was adapted from Tim Peters's list sort for Python ( TimSort).
Quicksort and mergesort are both O(n log n) in average performance. In the worst case, quicksort is O(n^2).
They moved to tuned merge sort because found that statistically for real partially sorted data sets this method may be a little faster than quick sort.
Collections.sort. Also, it said as fast as. I believe the main reason is still stability, though.Well Java 7 uses Timsort - a hybrid of Merge and insertion. As a matter of fact it's widely used - android, Octave,python use it too. http://en.wikipedia.org/wiki/Timsort
