151

Java 6's Arrays.sort method uses Quicksort for arrays of primitives and merge sort for arrays of objects. I believe that most of time Quicksort is faster than merge sort and costs less memory. My experiments support that, although both algorithms are O(n log(n)). So why are different algorithms used for different types?

rogerdpack
  • 62,887
  • 36
  • 269
  • 388
zjffdu
  • 25,496
  • 45
  • 109
  • 159
  • 21
    Quicksort worst case is N^2 not NlogN. – codaddict Sep 14 '10 at 08:27
  • Wait, what happens if you have an array of `Integer`s or something? – Tikhon Jelvis Sep 14 '10 at 08:30
  • 2
    Isn't this explained *in* the source you read? – Humphrey Bogart Sep 14 '10 at 10:11
  • 9
    This information is no longer current. Starting in Java SE 7, MergeSort has been replaced with [TimSort](http://en.wikipedia.org/wiki/Timsort) and QuickSort has been replaced with [Dual-Pivot QuickSort](http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf). See my answer below for links to the Java API docs. – Will Byrne May 08 '15 at 05:52
  • 1
    See also https://stackoverflow.com/questions/15154158/why-collections-sort-uses-merge-sort-instead-of-quicksort and for JDK 7+ see https://stackoverflow.com/questions/32334319/why-does-collections-sort-use-mergesort-but-arrays-sort-does-not?noredirect=1&lq=1 – rogerdpack Jul 03 '18 at 18:13
  • @codaddict Recent versions of the C++ library therefore use introsort, a version of quicksort that watches whether the recursion is getting too deep, and if so it switches to heapsort, which is O(n log n) in the worst case. This makes introsort O(n log n) in all cases without incurring the greater overhead of heapsort in every case. – Dinesh Kumar Mar 17 '19 at 19:13

6 Answers6

252

The most likely reason: quicksort is not stable, i.e. equal entries can change their relative position during the sort; among other things, this means that if you sort an already sorted array, it may not stay unchanged.

Since primitive types have no identity (there is no way to distinguish two ints with the same value), this does not matter for them. But for reference types, it could cause problems for some applications. Therefore, a stable merge sort is used for those.

OTOH, a reason not to use the (guaranteed n*log(n)) stable merge sort for primitive types might be that it requires making a clone of the array. For reference types, where the referred objects usually take up far more memory than the array of references, this generally does not matter. But for primitive types, cloning the array outright doubles the memory usage.

rogerdpack
  • 62,887
  • 36
  • 269
  • 388
Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
  • 1
    Another reason to use quicksort is that on the average case, quicksort is faster than mergesort. Although quicksort does more compares than mergesort, it does much less array accesses. 3-way quicksort can also achieve linear time if the input contains a lot of duplicated entries which is not unusual in practical applications (My guess is that dual pivot quick-sort also has this property ). – Jingguo Yao Feb 14 '16 at 06:53
  • 1
    For primitive types it doesn't clone the array, it can sort them in place, so I think the only reason is the stability contract, basically... – rogerdpack Jul 03 '18 at 18:24
37

According to Java 7 API docs cited in this answer, Arrays#Sort() for object arrays now uses TimSort, which is a hybrid of MergeSort and InsertionSort. On the other hand, Arrays#sort() for primitive arrays now uses Dual-Pivot QuickSort. These changes were implemented starting in Java SE 7.

Community
  • 1
  • 1
Will Byrne
  • 681
  • 7
  • 15
13

One reason I can think of is that quicksort has a worst case time complexity of O(n^2) while mergesort retains worst case time of O(n log n). For object arrays there is a fair expectation that there will be multiple duplicate object references which is one case where quicksort does worst.

There is a decent visual comparison of various algorithms, pay particular attention to the right-most graph for different algorithms.

msw
  • 42,753
  • 9
  • 87
  • 112
  • 3
    The java quicksort is a modified quicksort that does not derade to O(n^2), from the docs "This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance" – sbridges Jan 07 '12 at 17:46
10

I was taking Coursera class on Algorithms and in one of the lectures Professor Bob Sedgewick mentioning the assessment for Java system sort:

"If a programmer is using objects, maybe space is not a critically important consideration and the extra space used by a merge sort maybe not a problem. And if a programmer is using primitive types, maybe the performance is the most important thing so they use quick sort."

kukido
  • 10,431
  • 1
  • 45
  • 52
  • 8
    It is not the main reason. Right after that sentence there was a question, embedded into video about "Why for reference types is used MergeSort?" (because it's stable). I think Sedgewick didn't mention that in video to leave it for question. – likern Jul 26 '15 at 17:48
1

java.util.Arrays uses quicksort for primitive types such as int and mergesort for objects that implement Comparable or use a Comparator. The idea of using two different methods is that if a programmer’s using objects maybe space is not a critically important consideration and so the extra space used by mergesort maybe’s not a problem and if the programmer’s using primitive types maybe performance is the most important thing so use the quicksort.

For Example: This is the example when sorting stability matters.

enter image description here

That’s why stable sorts make sense for object types, especially mutable object types and object types with more data than just the sort key, and mergesort is such a sort. But for primitive types stability is not only irrelevant. It’s meaningless.

Source: INFO

Dinesh Kumar
  • 545
  • 4
  • 17
0

Java's Arrays.sort method uses quicksort, insertion sort and mergesort. There is even both a single and dual pivot quicksort implemented in the OpenJDK code. The fastest sorting algorithm depends on the circumstances and the winners are: insertion sort for small arrays (47 currently chosen), mergesort for mostly sorted arrays, and quicksort for the remaining arrays so Java's Array.sort() tries to choose the best algorithm to apply based on those criteria.

David McManamon
  • 385
  • 2
  • 10