Java & Merge Sort

Question

Why Java impl choose merge sort over quick sort? and why do they copy the content to an array?

API: "The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place."

Answer 1

Java guys traded the worst-case scenario with the avg case, as you probably know, quick sort might run in O(n^2) in the worst case..

You can read in the API, sorting a linked list in-place is more complex n^2log(n)

Merge sort is stable which the isn't true for the efficient version of quicksort. (which can be highly important upon sorting objects + many programmers take that as granted when they use Collections.sort())

Answer 2

The documentation gives the answer to both your questions:

This algorithm offers guaranteed n log(n) performance.

Merge sort doesn't have the pathological cases of quicksort

One further advantage of merge sort over quicksort is that merge sort is stable; quicksort is typically unstable. (Obviously with enough effort you can make it stable, but I believe it's relatively expensive to do so.)

This avoids the n² log(n) performance that would result from attempting to sort a linked list in place.

Copying into an array first means you're not relying on the complexity of the original collection's access to individual elements. I suppose it could look at whether the list implements RandomAccess and sort in place if so, but RandomAccess was only introduced in 1.4.

Answer 3

• Merge sort has guaranteed O(n log n) behaviour. Quick sort has a worst-case performance of O(n^2). So in some cases, merge sort is faster, and it has a better upper bound.

• An in-place sort like quick sort doesn't work on linked lists, as your quote mentions. To work predictably for all types of collections, a copy is needed.

• Quick sort by itself is not stable. Stability is sometimes desirable, and something that APIs should offer.

Answer 4

I believe the primary reason mergesort was chosen is because it is stable.

The n log n worst-case guarantee that others have mentioned is an advantage, but it is likely not the primary reason. If you look at the Arrays.sort methods, all the sorts on primitives use quicksort, and the sorts on Object[] use mergesort. This is because stable sort does not matter for primitives; equal primitives are not distinguishable from each other.