Quicksort is one of the best known sorting algorithms, judging by responses to interview questions. Everyone loves Quicksort because it is so straight forward to explain–

• Pick an element from the list, call it the pivot
• Split the list into parts greater and smaller than the pivot
• For these two sublists, repeat the procedure until you have one element or less

As much as I like quicksort, it is very hard to implement well but easy to implement poorly. As Bentley and McIlroy’s classic paper “Engineering a sort function” explains, there are many common implementation problems, including a lack of thread safety and terrible performance on certain inputs–

Yet in the summer of 1991 our colleagues Allan Wilks and Rick Becker found that a qsort run that should have taken a few minutes was chewing up hours of CPU time. Had they not interrupted it, it would have gone on for weeks. They found that it took n² comparisons to sort an ‘organ-pipe’ array of 2n integers: 123..nn.. 321.

Aside—McIlroy’s later paper A killer adversary for quicksort" explains how to construct the “organ-pipe” input.

Unable to find a good enough qsort, we set out to build a better one.

Bentley and McIlroy show how to mitigate the worst case by careful selection of a pivot, amongst other tricks. Instead of picking the first, or a random pivot, they argue for a dynamic scheme based on the array size–

With more effort finding a central element, we can push the number of comparisons closer to n lg n. […] Our final code therefore chooses the middle element of smaller arrays, the median of the first, middle and last elements of a mid-sized array, and the pseudo-median of nine evenly spaced elements of a large array.

There is one final improvement for quicksort. Almost twenty years later, Vladimir Yaroslavskiy found a beautiful trick to improve both the average and the worst case timings—Instead of one pivot, pick two—Dual Pivot Quicksort. Even Jon Bentley was impressed–

I think that Vladimir’s contributions to Quicksort go way beyond anything that I’ve ever done, and rank up there with Hoare’s original design and Sedgewick’s analysis — Jon Bentley From the openjdk discussion

It is reassuring to know we can always find new tricks for old algorithms. Using two elements instead of one is new to quicksort, but this trick surfaces in other places too. The power of two random choices: A survey of techniques and results shows that moving from one to two choices has a significant effect in load balancing–

….even a small amount of choice can lead to drastically different results in load balancing. Indeed, having just two random choices yields a large reduction in the maximum load over having one choice, while each additional choice beyond two decreases the maximum load by just a constant factor.

Similarly cuckoo hashing use a similar trick, using two hash functions instead of one to improve worse case performance. Still, if we are worried about the performance, sometimes it’s better to choose a different algorithm than tune another, as Bentley et al remark–

if worst-case performance is important, Quicksort is the wrong algorithm. (A quick memory fault might even be preferred to wasting weeks of cycles on a worst-case run.