Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Carl Mummert Mar 6 '12 at 19:20
3  
sorting-algorithms.com has a pretty thorough comparison of sorting algorithms. –  Joe Mar 6 '12 at 20:07
1  
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. –  Raphael Mar 7 '12 at 11:12
3  
This question won a recent contest on programmers.SE! –  Raphael Jun 18 '12 at 18:30
1  
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. –  Giorgio Jun 19 '13 at 22:31
show 5 more comments

10 Answers

up vote 73 down vote accepted

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

share|improve this answer
1  
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. –  Raphael Mar 7 '12 at 14:14
    
@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. –  Janoma Mar 8 '12 at 21:42
    
@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. –  Raphael Mar 8 '12 at 22:54
    
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. –  Jules Mar 24 '12 at 22:34
1  
@Sebastian: In the last sentence about "standard sort function in Java" you link to a wrong place: 1. There's no article available from there without registration. 2. The article can be found e.g. here and does not deal with Java at all. –  maaartinus May 29 '12 at 18:38
show 5 more comments

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.

share|improve this answer
    
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. –  Raphael Mar 7 '12 at 0:35
3  
@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. –  vonbrand Feb 1 '13 at 12:37
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
3  
@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. –  Gilles Mar 15 '12 at 23:21
    
@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. –  Raphael Mar 15 '12 at 23:23
3  
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. –  Dai Mar 15 '12 at 23:28
2  
This was also discussed here: cstheory.stackexchange.com/a/927/74 –  Jukka Suomela Mar 22 '12 at 11:44
add comment

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.

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

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:

share|improve this answer
3  
@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. –  Rafe Kettler Mar 6 '12 at 19:29
4  
@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. –  svick Mar 6 '12 at 19:32
1  
@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. –  Kaveh Mar 6 '12 at 19:34
1  
Heapsort is also in-place, why is QS often faster? –  Kevin Mar 6 '12 at 19:34
5  
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$. –  Carl Mummert Mar 6 '12 at 19:36
show 8 more comments

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.

share|improve this answer
1  
But what makes the constants so small? –  svick Mar 6 '12 at 20:23
    
@svick Because they are sorted in-place i.e., no extra memory is required. –  Sunil Mar 6 '12 at 20:31
    
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? –  Robert S. Barnes Apr 17 '13 at 7:56
add comment

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.

share|improve this answer
3  
Have you seen advanced in-place, iterative Quicksort implementations? They are many things but not "easy". –  Raphael Mar 10 '12 at 16:45
    
Number 2 does not answer my question at all, and numbers 1 and 3 need proper justification, in my opinion. –  Janoma Mar 12 '12 at 12:14
    
@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. –  MMS Mar 14 '12 at 20:25
add comment

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.

share|improve this answer
5  
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. –  Gilles Apr 10 '12 at 11:15
add comment

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 quick sort. A while later I wrote simple implentations of insertion sort, quick sort, heap sort and merge sort and tested these. My merge sort outperformed all the others while working on large data sets.

Since then, heap 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 quick sort 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 quick sort only to find out that it actually isn't quick sort. Sometimes the implementation switches between quick sort and another algorithm and sometimes it does not use quick sort 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 quick sort which a code comment calls "the slower algorithm".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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