Java: Arrays.sort quicksort and mergesort

Question

Possible Duplicate:
Why java Arrays use two different sort algorithms for different types?

So I was reading the Arrays doc on the various sort implementations. What I noticed was that some of the implementations used a tuned quicksort while others used a modified mergesort. Why the discrepancy?

Thanks!

score 26 · Accepted Answer · answered Apr 20 '12 at 18:37

26

Quicksort is used for arrays of primitive types while mergesort for Object[] arrays.

The main reason why mergesort is used for Objects that mergesort is stable - it does not reorder elements that are equal: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

For primitives the stability of the sort is meaningless, as you cannot distinguish two values that are equal. Hence, quicksort is used (except when sorting an array of Objects, for which mergesort is performed). Moreover, quicksort can be done in place, so there is no need to allocate another array.

answered Apr 20 '12 at 18:37

Eugene Retunsky

13,009
4
52
55

In today's world, mergesort has become the dominant sorter, as it can be implemented to use multiple cores – ControlAltDel Apr 20 '12 at 18:44
good point, but JDK doesn't use this for now. – Eugene Retunsky Apr 20 '12 at 18:51
5

That said, JDK 7 no longer uses mergesort -- it uses the mythical [TimSort](http://en.wikipedia.org/wiki/Timsort)! – Louis Wasserman Apr 20 '12 at 19:41
@LouisWasserman cool, thanks for that piece of info. any reason you refer to it as "mythical"? – OckhamsRazor Apr 22 '12 at 18:47
"Mythical" in that it's extremely complicated, and not many people understand it or would implement it themselves, but it's nevertheless scarily smart and fast. – Louis Wasserman Apr 22 '12 at 18:55

Java: Arrays.sort quicksort and mergesort

1 Answers1