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

http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types — zw324, May 16 '13 at 12:43
I know Yannis is going to show up and smack me for this, but this probably should be on Programmers. — Mike G, May 16 '13 at 12:49
And here is an answer of the author of the code http://stackoverflow.com/questions/15154158/why-collections-sort-is-using-merge-sort-insteadof-quicksort — Sanghyun Lee, Aug 13 '13 at 15:47

Marko Topolnik · Answer 1 · 2013-05-16T13:05:26.943

10

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

edited May 16 '13 at 13:05

answered May 16 '13 at 12:43

Marko Topolnik

195,646
29
319
436

1

Additional note: Insertion sort wins on small collections because it has a lower constant factor, which big-O doesn't record. Note that, for example: `n^2 < 10n` for `n < 10`. – Bernhard Barker May 16 '13 at 14:09
@Dukeling Yes, that's my point. Simplicity means low constant factor. – Marko Topolnik May 16 '13 at 14:10

score 1 · Answer 2 · edited May 23 '17 at 12:06

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

Andy Thomas · Answer 3 · 2013-05-16T12:52:07.360

1

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

edited May 16 '13 at 12:52

answered May 16 '13 at 12:45

Andy Thomas

84,978
11
107
151

1

Their average case is not O(n^2),, its O(nlogn). – Rami Jarrar May 16 '13 at 12:51
Thanks for catching that. I was focused on the n^2 worst-case, and typed it accidentally for average. – Andy Thomas May 16 '13 at 12:53

score 0 · Answer 4 · answered May 16 '13 at 12:43

0

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.

answered May 16 '13 at 12:43

AlexR

114,158
16
130
208

2

Java never used MergeSort for primitives, and never used QuickSort for reference types. – Marko Topolnik May 16 '13 at 12:50
2

Who is they? References, please. – zw324 May 16 '13 at 12:54
1

That is for `Collections.sort`. Also, it said as fast as. I believe the main reason is still stability, though. – zw324 May 16 '13 at 13:01

score 0 · Answer 5 · answered Oct 15 '13 at 11:56

0

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

answered Oct 15 '13 at 11:56

Struggler

672
2
9
22

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

5 Answers5