Why java Arrays use two different sort algorithms for different types ?

Question

Hi all,

I look at the source code of Arrays.java 's sort method, it uses quicksort for primitive type of array and merge sort for object type of array, what is the consideration ? I believe most of time quicksort is faster than merge sort and costs less memory, and my experiments approve that. Although they are both O(nlogn). So why here choose two different algorithms for different types ?

Thanks

Answer 1

The most likely reason: quicksort is not stable, i.e. equal entries can change their relative position during the sort; among other things, this means that if you sort an already sorted array, it may not stay unchanged.

Since primitive types have no identity (there is no way to distinguish two ints with the same value), this does not matter for them. But for reference types, it could cause problems for some applications. Therefore, a stable merge sort is used for those.

OTOH, a reason not to use the (guaranteed n*log(n)) merge sort for primitive types might be that it requires making a clone of the array. 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.

Answer 2

On reason I can think of is that quicksort has a worst case time complexity of O(n^2) while mergesort retains worst case time of O(n log n). For object arrays there is a fair expectation that there will be multiple duplicate object references which is one case where quicksort does worst.

There is a decent visual comparison of various algorithms, pay particular attention to the right-most graph for different algorithms.