QuickSort vs MergeSort on arrays of primitives in Java

Question

I know that Java's Arrays.sort method uses MergeSort for sorting arrays of objects (or collections of objects) since it is stable, and Java uses QuickSort for arrays of primitives because we don't need stability since two equal ints are indistinguishable, i.e. their identity doesn't matter.

My question is, in the case of primitives, why doesn't Java use MergeSort's guaranteed O(n log n) time and instead goes for the average O(n log n) time of QuickSort? In the last paragraph of one of the related answers here, it is explained that:

For reference types, where the referred objects usually take up far more memory than the array of references, this generally does not matter. But for primitive types, cloning the array outright doubles the memory usage.

What does this mean? Cloning a reference is still at-least as costly as cloning a primitive. Are there any other reasons for using QuickSort (average O(n log n)) instead of MergeSort (guaranteed O(n log n) time) on arrays of primitives?

Answer 1

Not all O(n log n) algorithms have the same constant factors. Quicksort, in the 99.9% of cases where it takes n log n time, runs in a much faster n log n than mergesort. I don't know the exact multiplier -- and it'll vary system to system -- but, say, quicksort could run twice as fast as merge sort on average and still have theoretical worst case n^2 performance.

Additionally, Quicksort doesn't require cloning the array in the first place, and merge sort inevitably does. But you don't have a choice for reference types if you want a stable sort, so you have to accept the copy, but you don't need to accept that cost for primitives.

Answer 2

Cloning a reference is still at-least as costly as cloning a primitive.

Most (or all?) implementations of Java implement an array of objects as an array of pointers (references) to objects. So cloning an array of pointers (references) would consume less space than cloning the objects themselves if the objects are larger in size than a pointer (reference).

I don't know why the term "cloning" was used. Merge sort allocates a second temp array, but the array is not a "clone" of the original. Instead an proper merge sort alternates the direction of merge from original to temp or from temp to original depending on iteration for bottom up, or depending on level of recursion for top down.

dual pivot quick sort

Based on what I can find doing web searches, Java's dual pivot quicksort keeps track of "recursions", and switches to heap sort if the recursion depth is excessive, to maintain O(n log(n)) time complexity, but at a higher cost factor.

quick sort versus merge sort

In addition to stability, merge sort can be faster for sorting an array of pointers (references) to objects. Merge sort does more moves (of the pointers) but fewer compares (of the objects accessed by dereferencing pointers), than quick sort.

On a system with 16 registers (most of them used as pointers), such as X86 in 64 bit mode, a 4-way merge sort is about as fast as regular quick sort, but I don't recall seeing a 4-way merge sort in a common library, at least not for a PC.