QuickSort vs MergeSort on Java primitive arrays

Question

I know that the Java method Arrays.sort uses MergeSort to sort arrays of objects (or collections of objects), because it is stable, and Java uses QuickSort for arrays of primitives, because we do not need stability, because two identical ints are indistinguishable, that is, they identity does not matter.

My question is, in the case of primitives, why does Java not use MergeSort, the guaranteed time is O (n log n), and instead goes for the average time O (n log n) QuickSort? The last paragraph of one of the related answers here explains that:

For reference types, where the mentioned objects usually occupy much more memory than an array of links, this usually does not matter. But for primitive types, array cloning directly doubles memory usage.

What does it mean? Cloning a link is still as expensive as cloning a primitive. Are there other reasons for using QuickSort (average O (n log n)) instead of MergeSort (guaranteed time O (n log n)) on primitive arrays?

Answer 1

Not all O (n log n) algorithms have the same constant factors. Quicksort, in 99.9% of cases when it takes n log n time, runs much faster n log n than mergesort. I don’t know the exact factor - and it will change in the system - but, say, quicksort can work twice as fast as average merge sorting, and still has the theoretical worst result of n ^ 2.

In addition, Quicksort does not require cloning an array in the first place, and merging sorting inevitably does. But you have no choice for reference types if you want stable sorting, so you need to accept a copy, but you do not need to accept this cost for primitives.

Answer 2

Arrays#sort(primitive array) does not use the traditional Quick Sort; it uses Double-Pivot Quicksort, which is faster than quicksort, which, in turn, is faster than merge sorting, in part because it does not have to be stable.

From javadoc:

Implementation note: The sorting algorithm is a two-line accelerator by Vladimir Yaroslavsky, John Bentley and Joshua Bloch. This algorithm offers O (n log (n)) performance on many datasets, which lead to performance degradation up to fast quadratic performance and, as a rule, faster than traditional (single-threaded) Quicksort implementations.

Answer 3

Cloning a link is still at least as expensive as cloning a primitive.

Most (or all?) Java implementations implement an array of objects as an array of pointers (references) to objects. Thus, cloning an array of pointers (links) will consume less space than cloning the objects themselves if the objects are larger than the pointer (link).

I do not know why the term "cloning" was used. Merge sort allocates a second temporary array, but the array is not a "clone" of the original. Instead, the correct type of merge alternates between the direction of the merge from the original to the tempo or from temp to the original, depending on iteration from bottom to top or depending on the recursion level for top to bottom.

double summary sorting

Based on what I can find in a web search, Java double pivot quicksort tracks “recursions” and switches to sorting the heap if the recursion depth is excessive to maintain O (n log (n)) time complexity, but with a higher cost ratio.

quick sort versus merge sort

In addition to stability, merge sorting can be faster for sorting an array of pointers (links) to objects. Merge sorting does more moves (pointers), but fewer comparisons (objects dereferencing pointers access) than quick sorting.

In a system with 16 registers (most of them are used as pointers), for example X86 in 64-bit mode, sorting with 4-way merge is about as fast as regular quick sorting, but I don’t remember to see 4 -way merge sort in a shared library, at least not for PC.

Answer 4

• QuickSort is about 40% faster than MergeSort on random data due to less data movement.
• QuickSort requires O (1) extra space, while MergeSort requires O (n)

PS Neither the classic QuickSort nor MergeSort are used in the standard Java library.