Why use two different algorithm for sorting arrays?

Question

In the Arrays class quick sort is used for sorting primitives but for sorting objects, it's merge sort.

I wonder why this is so?

• templatetypedef: Can you provide a link to what Java implementation you're talking about? This is not mandated by the JLS.
• Bozho: @templatetypedef it's not mandated, but is "an implementation note", and is the case in sun's implementation. The javadoc of Arrays clears this.
• BalusC: possible duplicate of Why does java.util.Arrays.sort(Object[]) use 2 kinds of sorting algorithms?
• templatetypedef: @Bozho- I agree... My question was mainly whether this was in Sun's implementation, or the OpenJDK, etc. so I could pull up the source myself.

Answer 1

The reason for using mergesort is that they want a stable algorithm - e.g. where equal objects (by compareTo() or compare()) are at the same relative order as before.

For primitives, equality implies "non-distinguish-ability". When sorting {5, 3, 5} to {3, 5, 5} it does not matter which of the fives was the first one before. So we can use the quicker (and non-stable) quicksort algorithm here.

Answer 2

Just a guess, but quicksort is O(n^2) in the worst case, while merge sort is stable (guaranteed O(n log n)).

The worst case for quicksort is triggered by equal values.. and equal primitives are identical, while "equal" objects may not be.

• Tomasz Nurkiewicz: stable (guaranteed O(n log n)) - being stable has nothing to do with pessimistic complexity. Stable sorting algorithm keeps the order of items that are considered equal.
• MarcB: You're correct. Brain fart, sorry :) However, merge sort returns more predictable execution times than quicksort which can vary from O(n log n) to O(n^2). That is what I meant, I shouldn't go around using the word stable when talking about sort algorithms^^
• Voo: And you've got to carefully craft your input data (though that can be a problem.. quite a fun way for a DDOS) to get anywhere near O(n^2) for quick sort which is usually faster than mergesort, because well constants DO matter. No the reason is just that no efficient quicksort implementation is stable which is a condition for the java library.