Why is quicksort better than other sorting algorithms in practice?

Question

^{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).

Answer 1

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.

Answer 2

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(n²) ) 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.

Answer 3

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.

Answer 4

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.

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

Answer 6

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.

Answer 7

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