Arrays.sort() -- two different strategies for primitive & complex data types to be sorted

Question

Arrays is sorting the primitive data types using the method DualPivotQuicksort, and the complex types separately-- using merge-sort. (insertion-sort if the input size is small).

DualPivotQuicksort is using merge-sort still on large input sizes, however, it is using dual-quicksort on a range of smaller input sizes.

What I am wondering is-- why this difference in strategies in sorting the primitive and non-primitives types?

The performance of the algorithm significantly depends on the input size-- not the data types. Invoking compareTo() instead of plain magnitude comparison on the primitives (>, <, ==) doesn't burn extra space in memory (and thus doesn't slow-down the absolute-time performance due to memory space) that would be considerable during run-time.

Why is Arrays.sort() methods using different sort strategies for the primitive data types, and for the complex data types?

TIA.

Answer 1

Because sorting reference types is guaranteed to be stable, whereas sorting primitives does not need to be (so quicksort, a non-stable sorting algorithm, can be used; merge sort on the other hand is in fact stable). Also note that quicksort is generally more optimal than mergesort (see this as well), which explains why it's taken advantage of when sorting primitives.

From Arrays.sort:

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.