31

This is a repost of a question on cs.SE by Janoma. Full credits and spoils to him or cs.SE.

In a standard algorithms course we are taught that quicksort is O(n log n) on average and O(n²) 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).

Improve this question
10
  • 3
    Quicksort reputation dates from a time when cache didn't exist.
    – AProgrammer
    May 29, 2012 at 9:20
  • 11
    "why does quicksort outperform other sorting algorithms in practice?" Sure that's true? Show us the real implementation you are refererring to with this statement, and the community will tell you why that specific implementation behaves the way it does. Everything else will lead to wild guessing about non-existent programs.
    – Doc Brown
    May 29, 2012 at 9:42
  • 1
    @DocBrown: Many Quicksort (or variants of it) implementations are chosen in many libraries, arguably because they perform best (I would hope so, that is). So there might just be something about the algorithm that makes Quicksort fast, independently of the implementation.
    – Raphael
    May 29, 2012 at 10:15
  • 1
    Someone has to say this for completeness, so I will: Quicksort is not (usually) stable. For this reason, you may not want to use it. Also, for this reason, your default sort may not be a Quicksort even when that is what you want.
    – RalphChapin
    May 29, 2012 at 14:18
  • 1
    @Raphael: Often what is called quick sort is actually some variation like intro sort (used, afaik, in the C++ standard library), not pure quick sort.
    – Giorgio
    May 29, 2012 at 17:20

7 Answers 7

Reset to default
23

I wouldn't agree that quicksort is better than other sorting algorithms in practice.

For most purposes, Timsort - the hybrid between mergesort/insertion sort which exploits the fact that the data you sort often starts out nearly sorted or reverse sorted.

The simplest quicksort (no random pivot) treats this potentially common case as O(N^2) (reducing to O(N lg N) with random pivots), while TimSort can handle these cases in O(N).

According to these benchmarks in C# comparing the built-in quicksort to TimSort, Timsort is significantly faster in the mostly sorted cases, and slightly faster in the random data case and TimSort gets better if the comparison function is particularly slow. I haven't repeated these benchmarks and would not be surprised if quicksort slightly beat TimSort for some combination of random data or if there is something quirky in C#'s builtin sort (based on quicksort) that is slowing it down. However, TimSort has distinct advantages when data may be partially sorted, and is roughly equal to quicksort in terms of speed when the data is not partially sorted.

TimSort also has an added bonus of being a stable sort, unlike quicksort. The only disadvantage of TimSort uses O(N) versus O(lg N) memory in the usual (fast) implementation.

Improve this answer
18

Quick sort is considered to be quicker because the coefficient is smaller that any other known algorithm. There is no reason or proof for that, just no algorithm with a smaller coefficient has been found. Its true that other algorithms also have O(n log n) time, but in the real world the coefficient is important also.

Note that for small data insertion sort (the one that is considered O(n2) ) is quicker because of the nature of the mathematical functions. This depends on the specific coefficients that vary from machine to machine. (At the end, only assembly is really running.) So sometimes a hybrid of quick sort and insertion sort is the quickest in practice I think.

Improve this answer
10
  • 7
    + Right. Teachers need to be more aware (and I was a teacher) of the fact that constant factors can vary by orders of magnitude. So the skill of performance tuning really matters, regardless of big-O. The problem is, they keep teaching gprof, only because they have to get past that bullet point in the curriculum, which is 180 degrees the wrong approach.
    – Mike Dunlavey
    May 29, 2012 at 14:50
  • 2
    “There is no reason or pro[o]f for that”: sure there is. If you dig deep enough, you'll find a reason.
    – Gilles 'SO- stop being evil'
    May 29, 2012 at 18:53
  • 2
    @B Seven: to simplify a lot… for an O(n log n) sort algorithm, there are (n log n) iterations of the sorting loop in order to sort n items. The coefficient is how long each cycle of the loop takes. When n is really big (at least thousands), coefficient doesn't matter as much as O() even if the coefficient is huge. But when n is small, coefficient matters – and can be the most important thing if you're only sorting 10 items.
    – Matt Gallagher
    May 30, 2012 at 15:25
  • 5
    @MikeDunlavey - a good example is that building the pyramids is O(n) while sorting your photos of them is O(n ln n) but which is quicker!
    – Martin Beckett
    May 30, 2012 at 15:52
  • 2
    There are guaranteed O(n log n) algorithms such as heapsort and mergesort, so in asymptotic worst-case terms Quicksort isn't even equally as fast as the best. But in real world performance, some quicksort variants do extremely well. However saying "the coefficient is smaller" is like saying "it's faster because it's faster". Why are the constant factors so small? A key reason is because quicksort is very good in locality terms - it makes very good use of caches. Mergesort has good locality too, but it's very hard to do in-place.
    – user8709
    May 30, 2012 at 18:55
16

Quicksort does not outperform all other sorting algorithms. For example, bottom-up heap sort (Wegener 2002) outperforms quicksort for reasonable amounts of data and is also an in-place algorithm. It is also easy to implement (at least, not harder than some optimized quicksort variant).

It is just not so well-known and you don't find it in many textbooks, that may explain why it is not as popular as quicksort.

Improve this answer
4
  • +1: I have run some tests and indeed merge sort was definitely better than quick sort for large arrays (> 100000 elements). Heap sort was slightly worse than merge sort (but merge sort needs more memory). I think what people call quick sort is often a variation called intro sort: quick sort that falls back to heap sort when the recursion depth goes beyond a certain limit.
    – Giorgio
    May 29, 2012 at 17:13
  • @Giorgio: quicksort can be modified in some ways to improve it, see for example here: algs4.cs.princeton.edu/23quicksort Did you try that improvements?
    – Doc Brown
    May 29, 2012 at 20:59
  • Interesting, can you lave a reference to a book\site to read more about it? (preferably a book)
    – Ramzi Kahil
    May 29, 2012 at 22:10
  • @Martin: you mean about Bottom-Up heapsort? Well, I gave a reference above. If you want a free resource, the german wikipedia has an article about it (de.wikipedia.org/wiki/BottomUp-Heapsort). Even if you don't speak german, I guess you can still read the C99 example.
    – Doc Brown
    May 30, 2012 at 5:49
7

You shouldn't center only on worst case and only on time complexity. It's more about average than worst, and it's about time and space.

Quicksort:

  • has an average time complexity of Θ(n log n);
  • can be implemented with space complexity of Θ(log n);

Also have in account that big O notation doesn't take in account any constants, but in practice it does make difference if the algorithm is few times faster. Θ(n log n) means, that algorithm executes in K n log(n), where K is constant. Quicksort is the comparison-sort algorithm with the lowest K.

Improve this answer
8
  • 1
    @Gilles: it has low K, because it's a simple algorithm.
    – vartec
    May 30, 2012 at 9:10
  • 6
    WTF? This doesn't make any sense. The simplicity of an algorithm has no relation with its running speed. Selection sort is simpler than quicksort, that doesn't make it faster.
    – Gilles 'SO- stop being evil'
    May 30, 2012 at 10:15
  • 1
    @Gilles: selection sort is O(n^2) for any case (worst, average and best). So it doesn't matter how simple it is. Quicksort is O(n log n) for average case, and among all algos with O(n log n) avg it's the simplest one.
    – vartec
    May 30, 2012 at 10:22
  • 1
    @Gilles: other things being equal, simplicity does aid performance. Say you're comparing two algorithms that each take (K n log n) iterations of their respective inner loops: the algorithm that needs to do less stuff per loop has a performance advantage.
    – comingstorm
    May 31, 2012 at 16:35
  • 2
    It may be, um, simple, but it's not a tautology, and it does relate to "simplicity". Many clever algorithms which seem like they ought to have a performance advantage turn out not to have one in practice, because the overhead outweighs the cleverness. Complexity is not the same as overhead, but they are not orthogonal, either.
    – comingstorm
    Jun 5, 2012 at 16:22
5

Quicksort is often a good choice as it is reasonably fast and reasonably quick and easy to implement.

If you are serious about sorting large amounts of data very quickly then you are probably better of with some variation on MergeSort. This can be made to take advantage of external storage, can make use of multiple threads or even processes but they are not trivial to code.

Improve this answer
1

The actual performance of algorithms depends on the platform, as well as the language, the compiler, programmer attention to implementation detail, specific optimization effort, et cetera. So, the "constant factor advantage" of quicksort isn't very well-defined -- it's a subjective judgement based on currently-available tools, and a rough estimation of "equivalent implementation effort" by whoever actually does the comparative performance study...

That said, I believe quicksort performs well (for randomized input) because it is simple, and because its recursive structure is relatively cache-friendly. On the other hand, because its worst case is easy to trigger, any practical use of a quicksort will need to be more complex than its textbook description would indicate: thus, modified versions such as introsort.

Over time, as the dominant platform changes, different algorithms may gain or lose their (ill-defined) relative advantage. Conventional wisdom on relative performance may well lag behind this shift, so if you're really unsure which algorithm is best for your application, you should implement both, and test them.

Improve this answer
7
  • I guess the "smaller constant" others relate it to is the one in formal analysis, that is on number of comparisons or swaps. This is very well defined but it is unclear how this translates to runtime. A colleague currently does some research on that, actually.
    – Raphael
    May 29, 2012 at 17:14
  • My impression was that it was about generalized performance, but I wouldn't count on either. You're right, though: if your comparison is particularly expensive, you can look up the number of expected comparisons...
    – comingstorm
    May 29, 2012 at 17:56
  • 1
    For the reason you state, talking about overall performance (time-wise) is not meaningul in the general case as too many details factor in. The reason for counting only select operations is not that they are expensive, but that they occur "most often" in the Landau-notation (Big-Oh) sense, so counting those gives you your rough asymptotics. As soon as you consider constants and/or runtime, this strategy is much less interesting.
    – Raphael
    May 29, 2012 at 18:04
  • A good implementation of QuickSort will compile such that your pivot values remain in a CPU register for as long as they are needed. This is often enough to beat a theoretically faster sort with comparable Big-O times.
    – Dan Lyons
    May 29, 2012 at 18:28
  • Different sort algorithms have different characteristics with respect to the number of comparisons and the number of interchanges they do. And @DanLyons note that a typical sort in a library performs its comparisons via user-supplied functions, and keeping values in registers across lots of function calls is pretty tricky.
    – Pointy
    May 30, 2012 at 21:36
0

Quicksort is fast, but only if you implement it very carefully.

Make sure that an array that is already sorted in correct or reverse order will be sorted quickly. This is a very common case, when an array is sorted twice. There are implementations that check first whether your array starts or ends in a subarray that is sorted in ascending or descending order. If the elements are random, then this will take very little time. If an array is sorted or the concatenation of two sorted arrays, then you can sort it in linear time. If you have n sorted items followed by fewer than O (n / log n) random items, you can sort it in linear time.

Really bad implementations will always choose the first or last element as the pivot, which turns Quicksort into Big-Theta(n^2) if the array is sorted; picking a random element as the pivot will help enormously.

Make sure that the implementation is fast if all or many elements are equal. With k equal elements, bad implementations will take k^2 operations for those elements, so if more than O (sqrt (n log n)) elements are equal, you won't be sorting in O (n log n) anymore.

Fine tuning: Consider the cost of a comparison and of moving elements. You can't avoid n log n comparisons, but you can sort with O (n) moves. If moving is substantially slower than comparing, you can sort an array of array indexes, get the exact order of indices for the correctly sorted array, and permute the elements. This may not be cache friendly, and uses extra storage for indices, so you may only want to do it if a subarray that you are partitioning fits into a cache.

Easier fine tuning: If moving elements is a lot more expensive than comparing, but not excessively: You reduce the number of moves by not picking the median as the pivot, but a bit of the median. So what you can do is pick 4 random elements and use the 2nd smallest or 2nd largest as the pivot. The number of comparisons grows, but the number of moves goes down.

Partial sorting: Sorting may be needed to display items in sorted order. But if you have tons of items, you can't display them all. You can put a million items into buckets according to the first letter, and if you want to display say items 330,000 to 330,025 you check which bucket they are in, and sort the one bucket containing the items you want. This can make things ten times faster.

Two cases where Quicksort is not the fastest by far: 1. Your array was sorted, but its values change slowly over time. Say weather stations sorted by temperature. One minute later the temperatures have changed slightly. Bubblesort might be fastest. 2. Your array was sorted, but a small number of random items has been changed, sometimes massively changed. If you have n items of which k are changed, you can sort them in O (n + k log k) which is linear if k = O (n / log n).

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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