Java: Arrays.sort quicksort and mergesort [duplicate]

Question

This question already has answers here:

Closed 13 years ago.

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!

Answer 1

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.

• ControlAltDel: In today's world, mergesort has become the dominant sorter, as it can be implemented to use multiple cores
• Eugene Retunsky: good point, but JDK doesn't use this for now.
• Louis Wasserman: That said, JDK 7 no longer uses mergesort -- it uses the mythical TimSort!
• OckhamsRazor: @LouisWasserman cool, thanks for that piece of info. any reason you refer to it as "mythical"?
• Louis Wasserman: "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.