Why is merge sort used by java to sort an array greater than elements 7

Question

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).

Answer 1

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 ≈ n²) 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).

Answer 2

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).

Answer 3

Quicksort and mergesort are both O(n log n) in average performance. In the worst case, quicksort is O(n^2).