3

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."

Improve this question
9
  • @Johannes ... the lesson is that the implementation details change. It is also possible that the material in one or both of the javadocs is out of date. Commented Aug 1, 2010 at 7:28
  • 2
    @Stephen C: If it's documented, especially with performance guarantees, it's not an implementation detail. Commented Aug 1, 2010 at 7:30
  • @Thomas I agree, the performance guarantee can't be an implementation detail. But the algorithm can be. Commented Aug 1, 2010 at 7:42
  • @Thomas - so how do you reconcile that with what @Johannes says about collection sorting changing from Java 6 to Java 7? They can and do change implementation details ... even if they are documented in the javadocs. Commented Aug 1, 2010 at 7:56
  • 1
    @NoozNooz42 - It would be a bad idea for the Java platform to do parallel sort by default. What if your platform is NOT a multi-core beast? What if you don't want sorting to use all available cores? What if the collections are too small for parallel sort to be effective? If you want your application to use parallel sorting, just use a third-party library ... Commented Aug 1, 2010 at 14:50

4 Answers 4

Reset to default
8

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())

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

6

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 n2 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.

Improve this answer

Comments

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.

Improve this answer

Comments

0

  • 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.

Improve this answer

1 Comment

bullet #2 is problematic since they did copy the content into an array anyway, so they could quicksort the array anyway...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.