181

What are the use cases when a particular sorting algorithm is preferred over others - merge sort vs QuickSort vs heapsort vs 'intro sort', etc?

Is there a recommended guide in using them based on the size, type of data structure, available memory and cache, and CPU performance?

user207421
  • 305,947
  • 44
  • 307
  • 483
sam
  • 1,847
  • 3
  • 13
  • 4

5 Answers5

339

First, a definition, since it's pretty important: A stable sort is one that's guaranteed not to reorder elements with identical keys.

Recommendations:

Quick sort: When you don't need a stable sort and average case performance matters more than worst case performance. A quick sort is O(N log N) on average, O(N^2) in the worst case. A good implementation uses O(log N) auxiliary storage in the form of stack space for recursion.

Merge sort: When you need a stable, O(N log N) sort, this is about your only option. The only downsides to it are that it uses O(N) auxiliary space and has a slightly larger constant than a quick sort. There are some in-place merge sorts, but AFAIK they are all either not stable or worse than O(N log N). Even the O(N log N) in place sorts have so much larger a constant than the plain old merge sort that they're more theoretical curiosities than useful algorithms.

Heap sort: When you don't need a stable sort and you care more about worst case performance than average case performance. It's guaranteed to be O(N log N), and uses O(1) auxiliary space, meaning that you won't unexpectedly run out of heap or stack space on very large inputs.

Introsort: This is a quick sort that switches to a heap sort after a certain recursion depth to get around quick sort's O(N^2) worst case. It's almost always better than a plain old quick sort, since you get the average case of a quick sort, with guaranteed O(N log N) performance. Probably the only reason to use a heap sort instead of this is in severely memory constrained systems where O(log N) stack space is practically significant.

Insertion sort: When N is guaranteed to be small, including as the base case of a quick sort or merge sort. While this is O(N^2), it has a very small constant and is a stable sort.

Bubble sort, selection sort: When you're doing something quick and dirty and for some reason you can't just use the standard library's sorting algorithm. The only advantage these have over insertion sort is being slightly easier to implement.

Non-comparison sorts: Under some fairly limited conditions it's possible to break the O(N log N) barrier and sort in O(N). Here are some cases where that's worth a try:

Counting sort: When you are sorting integers with a limited range.

Radix sort: When log(N) is significantly larger than K, where K is the number of radix digits.

Bucket sort: When you can guarantee that your input is approximately uniformly distributed.

dsimcha
  • 67,514
  • 53
  • 213
  • 334
  • 1
    As I recall, heap sort also has a very predictable running time in that there is little variation among different inputs of the same size, but that's of less interest than its constant space bound. I also find insertion sort the easiest to implement of the n^2 sorts, but maybe that's just me. Finally, you might also want to mention Shell sort, which is almost as simple to implement as insertion sort but has better performance, though still not n log n. – JaakkoK Dec 19 '09 at 20:48
  • 31
    Don't forget [Bogosort](http://en.wikipedia.org/wiki/Bogosort)! ;-) – Alex Brasetvik Dec 19 '09 at 21:02
  • 2
    +1 Very interesting. Would you care to explain how you can "guarantee ... approximately uniformly distributed." for Bucket Sort? – NNN Dec 19 '09 at 21:06
  • @drspod: You'd have to know something about the nature of your data and where it was coming from. This knowledge might come from the problem domain. There are no deep theoretical tricks to "guaranteeing your data is approximately uniformly distributed." – dsimcha Dec 19 '09 at 22:25
  • @dsimcha Do you just mean that the number of data within a range is bounded for all ranges? – NNN Dec 19 '09 at 22:54
  • It means that, within the range of values your data can take, all values have approximately equal probability. http://en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29 – dsimcha Dec 19 '09 at 23:03
  • I think saying Introsort is "almost always better than plain old quicksort" could be misleading. A Quicksort has the *possibility* of poor worst case performance, but it's *extremely* remote with a good implementation. Introsort is nearly *always* slower in return for eliminating what's normally a purely theoretical possibility. That's not to say it's a poor choice, only that you're trading slightly worse average performance in return for considerably better worst case performance. – Jerry Coffin Dec 20 '09 at 02:28
  • 2
    Why would introsort be substantially slower than quick sort? The only overhead is counting recursion depth, which should be negligible. It only switches after recursion is much deeper than it should be in a good quick sort case. – dsimcha Dec 20 '09 at 03:09
  • @dsimcha:The difference favoring quicksort is certainly quite small, but it's still there... – Jerry Coffin Dec 20 '09 at 05:35
  • @dsimcha Why not use heap sort for all the(general) cases? Heap sort is better quick sort. – Amit Tripathi Apr 28 '16 at 04:50
  • 2
    You fail to mention that the best case of bubble sort is O(n)! – Tara Sep 23 '16 at 04:29
  • mergesort is also easily parallelizable – philx_x Mar 24 '17 at 14:45
  • For small n, the selection sort have the use case when swaps or writes are expensiv and you need a stable sort (it use only n-1 swaps or 2(n-1) writes in the worst case). It is also used when somebody sort by hand on paper. A cycle sort have less wirtes but is not stable. – 12431234123412341234123 Jul 07 '17 at 09:01
  • 1
    Insertion sort is also very suitable when we know that elements are k position away from their original position and k is relatively small than N – Haider Ali Sep 10 '17 at 16:22
  • 1
    This is great and compact but you need to have a lot of prior knowledge about sorting to understand this. – Asif Feb 18 '19 at 07:11
  • What about the cases where data is random, nearly sorted? – Fawad Mar 20 '20 at 12:04
  • Supposedly, bubble sort has some niche uses where it is expected that the list is already sorted with just a few swaps needing to be performed and this comes up in computer graphics: https://en.wikipedia.org/wiki/Bubble_sort#Use – CubicInfinity Sep 12 '22 at 16:57
40

Quicksort is usually the fastest on average, but It has some pretty nasty worst-case behaviors. So if you have to guarantee no bad data gives you O(N^2), you should avoid it.

Merge-sort uses extra memory, but is particularly suitable for external sorting (i.e. huge files that don't fit into memory).

Heap-sort can sort in-place and doesn't have the worst case quadratic behavior, but on average is slower than quicksort in most cases.

Where only integers in a restricted range are involved, you can use some kind of radix sort to make it very fast.

In 99% of the cases, you'll be fine with the library sorts, which are usually based on quicksort.

roottraveller
  • 7,942
  • 7
  • 60
  • 65
Eli Bendersky
  • 263,248
  • 89
  • 350
  • 412
  • 9
    +1: For "In 99% of the cases, you'll be fine with the library sorts, which are usually based on quicksort". – Jim G. Dec 19 '09 at 19:13
  • Randomized pivoting gives Quicksort a runtime of O(nlogn) for all practical purposes, without needing any guarantees about bad data. I really don't think anyone implements a O(n^2) quicksort for any production code. – MAK Dec 19 '09 at 20:14
  • 2
    MAK, except, say, the C standard library qsort? (http://www.google.com/codesearch/p?hl=en&sa=N&cd=6&ct=rc#XAzRy8oK4zA/libc/stdlib/qsort.c&q=memmove%20android%20package:%22git://android.git.kernel.org/platform/bionic.git%22&d=1) - upon which most of the "production code" sorts rely – Eli Bendersky Dec 20 '09 at 04:50
  • Library sort is usally not based on quicksort, because it is not stable. Almost all higher languages (expect for C) provides a stable sort. In the most cases i know you need a stable, or at least a deterministic, sort. – 12431234123412341234123 Jul 12 '17 at 07:40
8

The Wikipedia page on sorting algorithms has a great comparison chart.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Dan Lorenc
  • 5,376
  • 1
  • 23
  • 34
3

What the provided links to comparisons/animations do not consider is when the amount of data exceed available memory --- at which point the number of passes over the data, i.e. I/O-costs, dominate the runtime. If you need to do that, read up on "external sorting" which usually cover variants of merge- and heap sorts.

http://corte.si/posts/code/visualisingsorting/index.html and http://corte.si/posts/code/timsort/index.html also have some cool images comparing various sorting algorithms.

Alex Brasetvik
  • 11,218
  • 2
  • 35
  • 36
0

@dsimcha wrote: Counting sort: When you are sorting integers with a limited range

I would change that to:

Counting sort: When you sort positive integers (0 - Integer.MAX_VALUE-2 due to the pigeonhole).

You can always get the max and min values as an efficiency heuristic in linear time as well.
Also you need at least n extra space for the intermediate array and it is stable obviously.

/**
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

(even though it actually will allow to MAX_VALUE-2) see: Do Java arrays have a maximum size?

Also I would explain that radix sort complexity is O(wn) for n keys which are integers of word size w. Sometimes w is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which all perform O(n log n) comparisons to sort n keys. However, in general w cannot be considered a constant: if all n keys are distinct, then w has to be at least log n for a random-access machine to be able to store them in memory, which gives at best a time complexity O(n log n). (from wikipedia)

Community
  • 1
  • 1
Droid Teahouse
  • 893
  • 8
  • 15