Why Merge sort is used for objects in Android/Java API?

Question

In Java Arrays.sort() for primitive type uses quick sort. On the other hand Arrays.sort() for objects uses Merge sort. And, same goes for Collection.sort() which also uses Merge sort. Collections sort uses Arrays sort implementation underneath. So, in simple sense i can say that primitives are sorted using quick sort but objects are sorted using Merge sort.

My guess is it has something to do with sorting algorithm it self. There are so many discussion on SO on Quick sort vs Merge sort, like this and this. Seems to be there are conflicting claims on which one is better, which is understandable as this depend on data sets.

My understanding is

• In place: Quick sort wins. Merge sort can be implemented in in-place for Linked list
• External Storage Data: Merge sort wins.
• Sorting List (backed by any form of linked list): Merge sort wins. Link

Android API seems to follow the same pattern as Java. This is what i found in Arrays.java

    public static void sort(long[] array) {
    DualPivotQuicksort.sort(array);
}

And this,

public static void sort(Object[] array) {
    ComparableTimSort.sort(array);
}

What i do not understand is, what makes Merge sort a good candidate for sorting objects in Java or in Android? Why not leaving this decision upto developers?

Answer 1

The key issue is sort stability - if two elements are equal from the point of view of the sort order, do they appear in the result in the same order as in the input.

It does not matter for e.g. long. All instances of 3 in the input will be grouped together, and nobody cares which was which.

On the other hand, objects may differ in ways that do not affect the sort order. If you are sorting animals by number of legs, you may care whether "cat" and "dog" stay in the original order or not.

The Arrays.sort mergesort is stable. The quicksort used for the primitives does not need to be stable.

Answer 2

Please see this answer: Why Collections.sort uses merge sort instead of quicksort?

TL;DR:

QuickSort has two major deficiencies when compared to mergesort:

1. It's not stable (as parsifal noted).
2. It doesn't guarantee n log n performance; it can degrade to quadratic performance on pathological inputs.