Take the 2-minute tour ×

Arrays.java's sort method uses quicksort for arrays of primitives and merge sort for arrays of objects. I believe that most of time quicksort is faster than merge sort and costs less memory. My experiments support that, although both algorithms are O(nlog(n)). So why are different algorithms used for different types?

share|improve this question
Quicksort worst case is N^2 not NlogN. –  codaddict Sep 14 '10 at 8:27
Wait, what happens if you have an array of Integers or something? –  Tikhon Jelvis Sep 14 '10 at 8:30
Isn't this explained in the source you read? –  Humphrey Bogart Sep 14 '10 at 10:11

3 Answers 3

up vote 70 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
+1 for my favorite site on the internet for today. –  Justin L. Sep 14 '10 at 9:52
The java quicksort is a modified quicksort that does not derade to O(n^2), from the docs "This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance" –  sbridges Jan 7 '12 at 17:46
"On many data sets" is not the same as "on all"... –  Puce Mar 1 '13 at 10:22

I was taking Coursera class on Algorithms and in one of the lectures Professor Bob Sedgewick mentioning the assessment for Java system sort:

"If a programmer is using objects, maybe space is not a critically important consideration and the extra space used by a merge sort maybe not a problem. And if a programmer is using primitive types, maybe the performance is the most important thing so they use quick sort."

share|improve this answer

Your Answer


