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.

Answer 3

I think the question of

what makes merge sort a good candidate for sorting Java objects and quick sort that for primitives ?

has been answered by others, but the question of

Why this decision has not been left to developers ?

has not yet been addressed.

The fact is, any developer can easily derive a new class from Collection or ArrayList and hide the sort() method (since sort() is a static method it must be hidden, not overidden) and use their own custom implementation of it.

The fact that this is rarely (if ever) done is perhaps because most young programmers of today have had more exposure to Java than C++. In the Java community, "abstraction" is taken to mean that you have no idea of how the underlying implementation of a class actually works, and moreover, that you don't need to. The machine-independence of the JVM has lulled our intuition of the speed/efficiency trade-offs. As a result, so many of us do not have as clear an understanding of data structures and algorithms as some of the older and more experienced programmers.

This is almost the opposite of the understanding of abstraction in C++. To quote Alex Stepanov:

As a matter of fact, I do not believe that a library could eliminate the need for a programmer to know algorithms and data structures. It only eliminates the need for a programmer to implement them. One needs to understand the fundamental properties of data structures to use them properly so that the application satisfies its own complexity requirements.

Answer 4

Merge sort is stable: equal elements will not be reordered as a result of the sort