379
$\begingroup$

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ in the worst case (like mergesort and heapsort), and even linear time in the best case (like bubblesort) but with some additional needs of memory.

After a quick glance at some more running times it is natural to say that quicksort should not be as efficient as others.

Also, consider that students learn in basic programming courses that recursion is not really good in general because it could use too much memory, etc. Therefore (and even though this is not a real argument), this gives the idea that quicksort might not be really good because it is a recursive algorithm.

Why, then, does quicksort outperform other sorting algorithms in practice? Does it have to do with the structure of real-world data? Does it have to do with the way memory works in computers? I know that some memories are way faster than others, but I don't know if that's the real reason for this counter-intuitive performance (when compared to theoretical estimates).


Update 1: a canonical answer is saying that the constants involved in the $O(n\log n)$ of the average case are smaller than the constants involved in other $O(n\log n)$ algorithms. However, I have yet to see a proper justification of this, with precise calculations instead of intuitive ideas only.

In any case, it seems like the real difference occurs, as some answers suggest, at memory level, where implementations take advantage of the internal structure of computers, using, for example, that cache memory is faster than RAM. The discussion is already interesting, but I'd still like to see more detail with respect to memory-management, since it appears that the answer has to do with it.


Update 2: There are several web pages offering a comparison of sorting algorithms, some fancier than others (most notably sorting-algorithms.com). Other than presenting a nice visual aid, this approach does not answer my question.

$\endgroup$
18
  • 4
    $\begingroup$ Merge sort is $O(n\log n)$ in the worst case, and sorting an array of integers where there is a known bound on the size of the integers can be done in $O(n)$ time with a counting sort. $\endgroup$ Mar 6, 2012 at 19:20
  • 17
    $\begingroup$ sorting-algorithms.com has a pretty thorough comparison of sorting algorithms. $\endgroup$
    – Joe
    Mar 6, 2012 at 20:07
  • 2
    $\begingroup$ Ad Update 1: I conjecture that you can have either rigorous analysis or realistic assumptions. I have not seen both. For instance, most formal analysis count only comparisons. $\endgroup$
    – Raphael
    Mar 7, 2012 at 11:12
  • 9
    $\begingroup$ This question won a recent contest on programmers.SE! $\endgroup$
    – Raphael
    Jun 18, 2012 at 18:30
  • 5
    $\begingroup$ Interesting question. I ran some tests some time ago with random data and a naive implementation of quick sort and merge sort. Both algorithms performed pretty well for small data sets (up to 100000 items) but after that merge sort turned out to be much better. This seems to contradict the general assumption that quick sort is so good and I still haven't found an explanation for it. The only idea I could come up with is that normally the term quick sort is used for more complex algorithms like intro sort, and that the naive implementation of quick sort with random pivot is not that good. $\endgroup$
    – Giorgio
    Jun 19, 2013 at 22:31

12 Answers 12

257
$\begingroup$

Short Answer

The cache efficiency argument has already been explained in detail. In addition, there is an intrinsic argument, why Quicksort is fast. If implemented like with two “crossing pointers”, e.g. here, the inner loops have a very small body. As this is the code executed most often, this pays off.

Long Answer

First of all,

The Average Case does not exist!

As best and worst case often are extremes rarely occurring in practice, average case analysis is done. But any average case analysis assume some distribution of inputs! For sorting, the typical choice is the random permutation model (tacitly assumed on Wikipedia).

Why $O$-Notation?

Discarding constants in analysis of algorithms is done for one main reason: If I am interested in exact running times, I need (relative) costs of all involved basic operations (even still ignoring caching issues, pipelining in modern processors ...). Mathematical analysis can count how often each instruction is executed, but running times of single instructions depend on processor details, e.g. whether a 32-bit integer multiplication takes as much time as addition.

There are two ways out:

  1. Fix some machine model.

    This is done in Don Knuth's book series “The Art of Computer Programming” for an artificial “typical” computer invented by the author. In volume 3 you find exact average case results for many sorting algorithms, e.g.

    • Quicksort: $ 11.667(n+1)\ln(n)-1.74n-18.74 $
    • Mergesort: $ 12.5 n \ln(n) $
    • Heapsort: $ 16 n \ln(n) +0.01n $
    • Insertionsort: $2.25n^2+7.75n-3ln(n)$ Runtimes of several sorting algorithms
      [source]

    These results indicate that Quicksort is fastest. But, it is only proved on Knuth's artificial machine, it does not necessarily imply anything for say your x86 PC. Note also that the algorithms relate differently for small inputs:
    Runtimes of several sorting algorithms for small inputs
    [source]

  2. Analyse abstract basic operations.

    For comparison based sorting, this typically is swaps and key comparisons. In Robert Sedgewick's books, e.g. “Algorithms”, this approach is pursued. You find there

    • Quicksort: $2n\ln(n)$ comparisons and $\frac13n\ln(n)$ swaps on average
    • Mergesort: $1.44n\ln(n)$ comparisons, but up to $8.66n\ln(n)$ array accesses (mergesort is not swap based, so we cannot count that).
    • Insertionsort: $\frac14n^2$ comparisons and $\frac14n^2$ swaps on average.

    As you see, this does not readily allow comparisons of algorithms as the exact runtime analysis, but results are independent from machine details.

Other input distributions

As noted above, average cases are always with respect to some input distribution, so one might consider ones other than random permutations. E.g. research has been done for Quicksort with equal elements and there is nice article on the standard sort function in Java

$\endgroup$
15
  • 8
    $\begingroup$ Results of type 2. can be transformed into results of type 1. by inserting machine-dependant constants. Therefore, I would argue 2. is a superior approach. $\endgroup$
    – Raphael
    Mar 7, 2012 at 14:14
  • 2
    $\begingroup$ @Raphael +1. I suppose you're assuming that machine-dependant is also implementation-dependant, right? I mean, fast machine + poor implementation is probably not very efficient. $\endgroup$
    – Janoma
    Mar 8, 2012 at 21:42
  • 2
    $\begingroup$ @Janoma I assumed the analyzed algorithm to be given in very detailed form (as the analysis is detailed) and the implementation to be as much by the letter as possible. But yes, the implementation would factor in as well. $\endgroup$
    – Raphael
    Mar 8, 2012 at 22:54
  • 6
    $\begingroup$ Actually, type 2 analysis is inferior in practice. Real world machines are so complicated that the results from type 2 can not be feasibly translated to type 1. Compare that to type 1: plotting experimental running times takes 5 minutes of work. $\endgroup$
    – Jules
    Mar 24, 2012 at 22:34
  • 5
    $\begingroup$ @Jules: "plotting experimental running time" is not type 1; it is no kind of formal analysis and it not transferable to other machines. That is why we do formal analysis, after all. $\endgroup$
    – Raphael
    Mar 24, 2012 at 22:53
99
$\begingroup$

There are multiple points that can be made regarding this question.

Quicksort is usually fast

Although Quicksort has worst-case $O(n^2)$ behaviour, it is usually fast: assuming random pivot selection, there's a very large chance we pick some number that separates the input into two similarly sized subsets, which is exactly what we want to have.

In particular, even if we pick a pivot that creates a 10%-90% split every 10 splits (which is a meh split), and a 1 element - $n-1$ element split otherwise (which is the worst split you can get), our running time is still $O(n \log n)$ (note that this would blow up the constants to a point that Merge sort is probably faster though).

Quicksort is usually faster than most sorts

Quicksort is usually faster than sorts that are slower than $O(n \log n)$ (say, Insertion sort with its $O(n^2)$ running time), simply because for large $n$ their running times explode.

A good reason why Quicksort is so fast in practice compared to most other $O(n \log n)$ algorithms such as Heapsort, is because it is relatively cache-efficient. Its running time is actually $O(\frac{n}{B} \log (\frac{n}{B}))$, where $B$ is the block size. Heapsort, on the other hand, doesn't have any such speedup: it's not at all accessing memory cache-efficiently.

The reason for this cache efficiency is that it linearly scans the input and linearly partitions the input. This means we can make the most of every cache load we do as we read every number we load into the cache before swapping that cache for another. In particular, the algorithm is cache-oblivious, which gives good cache performance for every cache level, which is another win.

Cache efficiency could be further improved to $O(\frac{n}{B} \log_{\frac{M}{B}} (\frac{n}{B}))$, where $M$ is the size of our main memory, if we use $k$-way Quicksort. Note that Mergesort also has the same cache-efficiency as Quicksort, and its k-way version in fact has better performance (through lower constant factors) if memory is a severe constrain. This gives rise to the next point: we'll need to compare Quicksort to Mergesort on other factors.

Quicksort is usually faster than Mergesort

This comparison is completely about constant factors (if we consider the typical case). In particular, the choice is between a suboptimal choice of the pivot for Quicksort versus the copy of the entire input for Mergesort (or the complexity of the algorithm needed to avoid this copying). It turns out that the former is more efficient: there's no theory behind this, it just happens to be faster.

Note that Quicksort will make more recursive calls, but allocating stack space is cheap (almost free in fact, as long as you don't blow the stack) and you re-use it. Allocating a giant block on the heap (or your hard drive, if $n$ is really large) is quite a bit more expensive, but both are $O(\log n)$ overheads that pale in comparison to the $O(n)$ work mentioned above.

Lastly, note that Quicksort is slightly sensitive to input that happens to be in the right order, in which case it can skip some swaps. Mergesort doesn't have any such optimizations, which also makes Quicksort a bit faster compared to Mergesort.

Use the sort that suits your needs

In conclusion: no sorting algorithm is always optimal. Choose whichever one suits your needs. If you need an algorithm that is the quickest for most cases, and you don't mind it might end up being a bit slow in rare cases, and you don't need a stable sort, use Quicksort. Otherwise, use the algorithm that suits your needs better.

$\endgroup$
7
  • 5
    $\begingroup$ Your last remark is especially valuable. A colleague of mine currently analyses Quicksort implementations under different input distributions. Some of them break down for many duplicates, for instance. $\endgroup$
    – Raphael
    Mar 7, 2012 at 0:35
  • 4
    $\begingroup$ @Raphael, take a look at McIllroy's "A Killer Adversary for Quicksort", Software - Practice and Experience 29(4), 341-344 (1999). It describes a devious technique to make Quicksort take $O(n^2)$ time always. Bentley and McIllroy's "Engineering a Sort Function", Software - Practice and Experience 23(11), 1249-1265 (1993) might also be relevant. $\endgroup$
    – vonbrand
    Feb 1, 2013 at 12:37
  • 11
    $\begingroup$ "[T]here's no theory behind this, it just happens to be faster." That statement is highly unsatisfactory from a scientific point of view. Imagine Newton saying, "Butterflies fly up, apples fall down: there's no theory behind this, apples just happen to fall." $\endgroup$ Jul 24, 2014 at 9:01
  • 2
    $\begingroup$ @Alex ten Brink, what do you mean with “In particular, the algorithm is cache-oblivious”? $\endgroup$
    – Hibou57
    Jul 24, 2014 at 20:19
  • 5
    $\begingroup$ @David Richerby, “That statement is highly unsatisfactory from a scientific point of view”: he may be just witnessing a fact without pretending we should be happy with it. Some algorithm families suffers from a lack of full formalisation; hashing functions are an example case. $\endgroup$
    – Hibou57
    Jul 24, 2014 at 20:31
55
$\begingroup$

In one of the programming tutorials at my university, we asked students to compare the performance of quicksort, mergesort, insertion sort vs. Python's built-in list.sort (called Timsort). The experimental results surprised me deeply since the built-in list.sort performed so much better than other sorting algorithms, even with instances that easily made quicksort, mergesort crash. So it's premature to conclude that the usual quicksort implementation is the best in practice. But I'm sure there much better implementation of quicksort, or some hybrid version of it out there.

This is a nice blog article by David R. MacIver explaining Timsort as a form of adaptive mergesort.

$\endgroup$
6
  • 26
    $\begingroup$ @Raphael To put it succintly, Timsort is merge sort for the asymptotics plus insertion sort for short inputs plus some heuristics to cope efficiently with data that has the occasional already-sorted burst (which happens often in practice). Dai: in addition to the algorithm, list.sort benefits from being a built-in function optimized by professionals. A fairer comparison would have all functions written in the same language at the same level of effort. $\endgroup$ Mar 15, 2012 at 23:21
  • 2
    $\begingroup$ @Dai: You could at least describe with what kind of inputs (resp. their distribution) under which circumstances (low RAM, did one implementation parallelise, ...) you obtained your results. $\endgroup$
    – Raphael
    Mar 15, 2012 at 23:23
  • 9
    $\begingroup$ We tested on list of random numbers, and partially sorted, completely sorted, and reversely sorted. It was an introductory 1st year course, so it wasn't a deep empirical study. But the fact that it is now officially used to sort arrays in Java SE 7 and on the Android platform does mean something. $\endgroup$
    – Dai
    Mar 15, 2012 at 23:28
  • 4
    $\begingroup$ This was also discussed here: cstheory.stackexchange.com/a/927/74 $\endgroup$ Mar 22, 2012 at 11:44
  • 1
    $\begingroup$ I suspect that quick sort, merge sort and insertion sort were implemented in python, while the list.sort implementation was written in C or C++. And list.sort was properly highly optimised because it is quite important for overall performance, while the other algorithms were implemented as a student exercise. Let your students add an implementation of Timsort as well. $\endgroup$
    – gnasher729
    Apr 8, 2022 at 11:43
40
$\begingroup$

I think one of the main reasons why QuickSort is so fast compared with other sorting algorithms is because it's cache-friendly. When QS processes a segment of an array, it accesses elements at the beginning and end of the segment, and moves towards the center of the segment.

So, when you start, you access the first element in the array and a piece of memory (“location”) is loaded into the cache. And when you try to access the second element, it's (most likely) already in the cache, so it's very fast.

Other algorithms like heapsort don't work like this, they jump in the array a lot, which makes them slower.

$\endgroup$
6
  • 6
    $\begingroup$ That's disputable explanation: mergesort is cache friendly too. $\endgroup$ Mar 6, 2012 at 22:46
  • 3
    $\begingroup$ I think this answer is basically right, but here's some details youtube.com/watch?v=aMnn0Jq0J-E $\endgroup$
    – rgrig
    Mar 6, 2012 at 22:50
  • 3
    $\begingroup$ probably the multiplicative constant for the average case time complexity of quick-sort is also better (independent of the cache factor you have mentioned). $\endgroup$
    – Kaveh
    Mar 6, 2012 at 23:10
  • 1
    $\begingroup$ The point you mentioned is not that important, compared to other good properties of quick sort. $\endgroup$
    – MMS
    Mar 10, 2012 at 16:04
  • 1
    $\begingroup$ @Kaveh: "the multiplicative constant for the average case time complexity of quick-sort is also better" Do you have any data on this? $\endgroup$
    – Giorgio
    Apr 28, 2012 at 18:23
30
$\begingroup$

Others have already said that the asymptotic average runtime of Quicksort is better (in the constant) than that of other sorting algorithms (in certain settings).

What does that mean? Assume any permutation is chosen at random (assuming uniform distribution). In this case, typical pivot selection methods provide pivots that in expectation divide the list/array roughly in half; that is what brings us down to $\cal{O}(n \log n)$. But, additionally, merging partial solutions obtained by recursing takes only constant time (as opposed to linear time in case of Mergesort). Of course, separating the input in two lists according to the pivot is in linear time, but it often requires few actual swaps.

Note that there are many variants of Quicksort (see e.g. Sedgewick's dissertation). They perform differently on different input distributions (uniform, almost sorted, almost inversely sorted, many duplicates, ...), and other algorithms might be better for some.

Another fact worth noting is that Quicksort is slow on short inputs compared to simper algorithms with less overhead. Therefore, good libraries do not recurse down to lists of length one but will use (for example) insertion sort if input length is smaller than some $k \approx 10$.

$\endgroup$
23
$\begingroup$

In comparison to other comparison-based sorting algorithms with $O(n \lg n)$ time complexity, quick-sort is often considered to better than other algorithms like merge-sort because it is an in-place sorting algorithm. In other words, we don't need (much more) memory to store the members of the array.

ps: to be precise, being better than other algorithms is task dependent. For some tasks it might be better to use other sorting algorithms.

See also:

$\endgroup$
13
  • 3
    $\begingroup$ @Janoma this is a matter of what language and compiler you use. Almost all functional languages (ML, Lisp, Haskell) can do optimizations that prevent the stack from growing, and smarter compilers for imperative languages can do the same (GCC, G++, and I believe MSVC all do this). The notable exception is Java, which will never do this optimization, so it makes sense in Java to rewrite your recursion as iteration. $\endgroup$ Mar 6, 2012 at 19:29
  • 4
    $\begingroup$ @J.D., you can't use tail call optimization with quicksort (at least not completely), because it calls itself twice. You can optimize away the second call, but not the first call. $\endgroup$
    – svick
    Mar 6, 2012 at 19:32
  • 1
    $\begingroup$ @Janoma, you don't really need the recursive implementation. For example, if you look at the implementation of the qsort function in C, it does not use recursive calls, and therefore the implementation becomes much faster. $\endgroup$
    – Kaveh
    Mar 6, 2012 at 19:34
  • 1
    $\begingroup$ Heapsort is also in-place, why is QS often faster? $\endgroup$
    – Kevin
    Mar 6, 2012 at 19:34
  • 9
    $\begingroup$ Even without stack optimization, if the recursion cuts down the size of the input by half each time, then the recursions will never grow very deep, because the memory is just not that big. You could do an in-place recursive sort of all the bytes of an entire $2^{32}$ byte memory without ever growing the stack depth beyond $40$. $\endgroup$ Mar 6, 2012 at 19:36
19
$\begingroup$

My experience working with real world data is that quicksort is a poor choice. Quicksort works well with random data, but real world data is most often not random.

Back in 2008 I tracked a hanging software bug down to the use of quicksort. A while later I wrote simple implentations of insertion sort, quicksort, heap sort and merge sort and tested these. My merge sort outperformed all the others while working on large data sets.

Since then, merge sort is my sorting algorithm of choice. It is elegant. It is simple to implement. It is a stable sort. It does not degenerate to quadratic behaviour like quicksort does. I switch to insertion sort to sort small arrays.

On many occasions I have found my self thinking that a given implementation works surprisingly well for quicksort only to find out that it actually isn't quicksort. Sometimes the implementation switches between quicksort and another algorithm and sometimes it does not use quicksort at all. As an example, GLibc's qsort() functions actually uses merge sort. Only if allocating the working space fails does it fall back to in-place quicksort which a code comment calls "the slower algorithm".

Edit: Programming languages such as Java, Python and Perl also use merge sort, or more precisely a derivative, such as Timsort or merge sort for large sets and insertion sort for small sets. (Java also uses dual-pivot quicksort which is faster than plain quicksort.)

$\endgroup$
3
  • $\begingroup$ I had seen something similar to this because we happened to be constantly appending/resorting to insert into a batch of already sorted data. You can work around this on average by using a randomized quicksort (and get surprised by a rare and random terribly slow sort), or you can tolerate an always slower sort that never takes a surprising amount of time to finish. Sometimes you require sort stability as well. Java has gone from using merge sort to a quicksort variant. $\endgroup$
    – Rob
    Mar 4, 2015 at 19:54
  • 1
    $\begingroup$ @Rob This is not accurate. Java still uses a variant of mergesort (Timsort) to this day. It does use a variant of quicksort, too (dual-pivot quicksort). $\endgroup$ Jun 23, 2015 at 15:04
  • $\begingroup$ Details between a simple implementation and a slightly more detailed one can make a big difference. For already sorted, or reverse sorted, the difference between "use the first element as pivot" and "sort the first, middle and last elements, use the new middle" is huge. (Or randomised, but when I had to fix a slow buggy implementation of quicksort, I didn't try that.) $\endgroup$
    – armb
    Jan 18, 2020 at 9:46
17
$\begingroup$

Even though quick-sort has a worst case run time of $\Theta(n^2)$, quicksort is considered the best sorting because it is VERY efficient on the average: its expected running time is $\Theta(n\log n)$ where the constants are VERY SMALL compared to other sorting algorithms. This is the main reason for using quick sort over other sorting algorithms.

The second reason is that it performs in-place sorting and works very well with virtual-memory environments.

UPDATE: : (After Janoma's and Svick's comments)

To illustrate this better let me give an example using Merge Sort (because Merge sort is the next widely adopted sort algorithm after quick sort, I think) and tell you where the extra constants come from (to the best of my knowledge and why I think Quick sort is better):

Consider the following seqence:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

If you care fully look how the last stage is happening, first 12 is compared with 8 and 8 is smaller so it goes first. Now 12 is AGAIN compared with 21 and 12 goes next and so on and so forth. If you take the final merge i.e. 4 elements with 4 other elements, it incurs a lot of EXTRA comparisons as constants which is NOT incurred in Quick Sort. This is the reason why quick sort is preferred.

$\endgroup$
3
  • 1
    $\begingroup$ But what makes the constants so small? $\endgroup$
    – svick
    Mar 6, 2012 at 20:23
  • 1
    $\begingroup$ @svick Because they are sorted in-place i.e., no extra memory is required. $\endgroup$
    – 0x0
    Mar 6, 2012 at 20:31
  • $\begingroup$ Wouldn't a better comparison be between quicksort and heapsort, since heapsort is $\Theta(n \lg n)$ in all cases and also in place like quicksort? $\endgroup$ Apr 17, 2013 at 7:56
17
$\begingroup$

Under what conditions is a specific sorting algorithm actually the fastest one?

  1. When implemented in a parallel way in hardware, does it need to have a reasonably low latency while requiring as few gates as possible?

    Yes, use a bitonic sorter or Batcher odd-even mergesort, latency is $\Theta(\log(n)^2)$ and the number of comparators and multiplexers is $\Theta(n \cdot \log(n)^2)$.

  2. How many different values can each element have? Can every possible value have assigned a unique place in memory or cache?

    Yes, use count sort or radix sort, those usually have a linear runtime of $\Theta(n \cdot k)$ (count sort) or $\Theta(n \cdot m)$ (bucket sort) but slow down for a large number of different values, as $k=2^{\#number\_of\_Possible\_values}$ and $m = \#maximum\_length\_of\_keys$.

  3. Does the underlying data structure consist of linked elements?

    Yes, always use in-place merge sort. There are both easy to implement fixed size or adaptive (a.k.a. natural) bottom-up in place merge sorts of different arities for linked data structures, and since they never require copying the entire data in each step and they never require recursions either, they are faster than any other general comparison-based sorts, even faster than quick sort.

  4. Does the sorting need to be stable?

    Yes, use mergesort, either in place or not, fixed-size or adaptive, depending on the underlying data structure and the kind of data to be expected, even in cases where quick sort would otherwise be preferred, as stabilizing an arbitrary sorting algorithm requires $\Theta(n)$ additional memory in the worst case consisting of original indexes, which also needs to be kept in sync with each swap that is to be performed on the input data, so that every performance gain that quick sort might have over merge sort is probably thwarted.

  5. Can the size of the underlying data be bound to a small to medium size? e.g. Is n < 10,000...100,000,000 (depending on the underlying architecture and data structure)?

    use bitonic sort or Batcher odd-even mergesort. Go to #1

  6. Can you spare another $\Theta(n)$ memory?

    Yes

    • Does the input data consist of large pieces of already sorted sequential data?

    • use adaptive (aka natural) merge sort or timsort

    • Does the input data mostly consist of elements that are almost in the correct place?

    • Use bubble sort or insertion sort. If you fear their $\Theta(n^2)$ time complexity (which is pathological for almost sorted data), maybe consider switching to shell sort with an (almost) asymptotically optimal sequence of gaps, some sequences that yield $\Theta(n \cdot \log(n)^2)$ worst case run time are known, or maybe try comb sort. I'm not sure either shell sort or comb sort would perform reasonably good in practice.

    No

    • Can you spare another $\Theta(\log(n))$ memory? Yes

    • Does the underlying data structure allow for directed sequential access or better?

    • Yes

      • Does it allow only a single sequence of read/write accesses at a time up till the end of the data has been reached (e.g. directed tape access)?
      • Yes, use merge sort, but there is no obvious way to make this case in place, so it may require additional $\Theta(n)$ memory. But if you have time and the balls to do it, there is a way to merge 2 arrays in $\Theta(n)$ time using only $\Theta(\log(n))$ space in a stable way, according to Donald E. Knuth "The Art of Computer Programming, Volume 3: Sorting and Searching", exercise 5.5.3. states that there is an algorithm by L. Trabb-Pardo that does so. However, I doubt this would be any faster than the naive mergesort version or the quicksort from the case above.

      • No, it allows multiple simultaneous accesses to a sequence of data (e.g. is not a tape drive) use quicksort, for practical purposes I would recommend either a randomized or an approximated median one. If you are wary of pathological $\Theta(n^2)$ cases, consider using intro sort. If you are hell-bent on deterministic behavior, consider using the median-of-median algorithm to select the pivot element, it requires $\Theta(n)$ time and its naive implementation requires $\Theta(n)$ space (parallelizable), whereas it may be implemented to only require $\Theta(\log(n))$ space (not parallelizable). However, the median-of-median algorithm gives you a deterministic quicksort which has worst-case $\Theta(n \cdot \log(n))$ run-time.

    • No, you're screwed (sorry, we need at least 1 way of accessing each data element once)

      • No, Can you spare a small constant amount of memory?
      • Yes, Does the underlying data structure allow for random access?
        • Yes, use heapsort, it has an asymptotic optimal run-time of $\Theta(n \cdot \log(n))$, but dismal cache coherency and doesn't parallelize well.
        • No, you are screwed
      • No, you are screwed

Implementation hints for quicksort

  • Naive binary quicksort requires $\Theta(n)$ additional memory, however, it is relatively easy to reduce that down to $\Theta(\log(n))$ by rewriting the last recursion call into a loop. Doing the same for k-ary quicksorts for k > 2 requires $\Theta(n^{\log_k(k-1)})$ space (according to the master theorem), so binary quicksort requires the least amount of memory, but I would be delighted to hear if anyone knows whether k-ary quicksort for k > 2 might be faster than binary quicksort on some real world setup.

  • There exist bottom-up, iterative variants of quicksort, but AFAIK, they have the same asymptotic space and time boundaries as the top-down ones, with the additional down sides of being difficult to implement (e.g. explicitly managing a queue). My experience is that for any practical purposes, those are never worth considering.

Implementation hints for mergesort

  • bottom-up mergesort is always faster than top-down mergesort, as it requires no recursion calls.

  • the very naive mergesort may be sped up by using a double buffer and switch the buffer instead of copying the data back from the temporal array after each step.

  • For many real-world data, adaptive mergesort is much faster than a fixed-size mergesort.

  • the merge algorithm can easily be parallelized by splitting the input data into k approximately same-sized parts. This will require k references into data, and it is a good thing to choose k such that all of k (or c*k for a small constant c >= 1) fit into the nearest memory hierarchy(usually L1 data cache). Choosing the smallest out of k elements the naive way(linear search) takes $\Theta(k)$ time, whereas building up a min-heap within those k elements and choosing the smallest one requires only amortized $\Theta(\log(k))$ time (picking the minimum is $\Theta(1)$ of course, but we need to do a little maintenance as one element is removed and replaced by another one in each step).

  • The parallelized merge always requires $\Theta(n)$ memory regardless of k.

  • From what I have written, it is clear that quicksort often isn't the fastest algorithm, except when the following conditions all apply:

  • there are more than a "few" possible values

  • the underlying data structure is not linked

  • we do not need a stable order

  • data is big enough that the slight sub-optimal asymptotic run-time of a bitonic sorter or Batcher odd-even mergesort kicks in

  • the data isn't almost sorted and doesn't consist of bigger already sorted parts

  • we can access the data sequence simultaneously from multiple places

  • memory writes are particularly expensive (because that's mergesort's main disadvantage), so far as it slows down the algorithm beyond a quicksort's probable sub-optimal split. or we can only have $\Theta(\log(n))$ additional memory, $\Theta(n)$ is too much (e.g. external storage)

$\endgroup$
2
  • $\begingroup$ (5): Apple's sort implementation checks one run in ascending or descending order both at the beginning and the end of the array first. This is very quick if there are not many such elements, and can handle these elements very effectively if there are more than n / ln n of them. Concatenate two sorted arrays and sort the result, and you get a merge $\endgroup$
    – gnasher729
    Jul 9, 2016 at 13:03
  • $\begingroup$ I got tired of googling for it, IIRC Facebook or Google created a library that explored the data before deciding which algorithm to use, I thought it was called F15 or something $\endgroup$
    – SDReyes
    Jan 21, 2020 at 14:37
16
$\begingroup$

1 - Quick sort is inplace (doesn't need extra memmory, other than a constant amount.)

2 - Quick sort is easier to implement than other efficient sorting algorithms.

3 - Quick sort has smaller constant factors in it's running time than other efficient sorting algorithms.

Update: For merge sort, you need to do some "merging," which needs extra array(s) to store the data before merging; but in quick sort, you don't. That's why quick sort is in-place. There are also some extra comparisons made for merging which increase constant factors in merge sort.

$\endgroup$
4
  • 5
    $\begingroup$ Have you seen advanced in-place, iterative Quicksort implementations? They are many things but not "easy". $\endgroup$
    – Raphael
    Mar 10, 2012 at 16:45
  • 2
    $\begingroup$ Number 2 does not answer my question at all, and numbers 1 and 3 need proper justification, in my opinion. $\endgroup$
    – Janoma
    Mar 12, 2012 at 12:14
  • $\begingroup$ @Raphael: They ARE easy. It's much easier to implement quick sort in-place using an array, instead of pointers. And it doesn't need to be iterative to be in-place. $\endgroup$
    – MMS
    Mar 14, 2012 at 20:25
  • $\begingroup$ The arrays for merging aren't that bad. Once you have moved one item from a source pile to the destination pile, it no longer needs to be there. If you're using dynamic arrays, there is constant memory overhead when merging. $\endgroup$
    – Oskar Skog
    Jun 30, 2017 at 20:20
10
$\begingroup$

Most of the sortings methods have to move data around in short steps (for example, merge sort makes changes locally, then merges this small piece of data, then merges a bigger one. ..). In consequence, you need many data movements if data is far from its destination.

Quicksort, on the other side tries to interchange numbers that are in the first part of the memory and are big, with numbers that are in the second part of the array and are small (if you are sorting $a \le b$, the argument is the same in the other sense), so they get quickly allocated near their final destination.

$\endgroup$
1
  • 5
    $\begingroup$ Your argument about quicksort vs merge sort doesn't hold water. Quicksort starts with a large move, then makes smaller and smaller moves (about half as large at each step). Merge sort starts with a small move, then makes larger and larger moves (about twice as large at each step). This doesn't point to one being more efficient than the other. $\endgroup$ Apr 10, 2012 at 11:15
3
$\begingroup$

You switched in your question from "is better" to "has better runtime". These are not the same. If you look at the other answers, you will find that Mergesort might run faster - but Quicksort has the advantage that it uses negligible space for things other than the array to be sorted. That means I can call it without fear of running out of memory, no matter how large the array is. That is not quite true for Mergesort, if the data can be close in size to the available data. And if virtual memory is available, Mergesort can take a lot longer due to paging.

In practice you wouldn't just use a O (n log n) algorithm, you would check if you can do things faster in special cases. If your array is mostly ascending or mostly descending with few exceptions, it can be sorted in linear time. (If let's say all but 1/8th of the values are in ascending order, it can be sorted in O (n log n), but much faster than using Quicksort or Mergesort).

If you go a bit further: If your array consists of an initial part that is mostly sorted, a middle part, and an end part that is mostly sorted, and the middle part is substantially smaller than the whole array, then we can sort the middle part with Quicksort or Mergesort, and combine the result with the sorted initial or end parts. However, this doesn't affect the question, because the middle part can still be sorted with Quicksort or Mergesort.

Another question is: Can the work be multi-threaded? The partitioning is hard to divide between two threads. Once the array is partitioned, each half can easily be handled by a separate thread. If you have many threads, being able to use only one for the initial partitioning is painful. With Mergesort, we can also do many smaller merges using many threads. We have the advantage that a single merge can also be run in parallel by one thread producing the lower half of the sorted array, and another thread working from the high values down, producing the higher half of the sorted array. I think this gives a large advantage to Mergesort if many threads are available.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.