It gets even quicker, faster sorting with Pattern-defeating Quicksort


this is a classic computer science bachelor topic: Sorting algorithms, implementing them and in the figuring out that Quicksort is the fastest you can get (by divide-n-conquer).

Hence, it amazed me to find out there is a new even faster Quicksort called Pattern defeating Quicksort, it not only uses Quicksort internally but jumps to other algorithms if suitable as well. Only downside, it only works on medium-sized data sets (as everything has to fit in RAM).

The paper this week is the initial proof of this new algorithm. Warning: It is quite mathematical as of why I also linked you a YouTube video explaining it.


A new solution for the Dutch national flag problem is proposed, requiring no three-way comparisons, which gives quicksort a proper worst-case runtime of O(nk) for inputs with k distinct elements. This is used together with other known and novel techniques to construct a hybrid sort that is never significantly slower than regular quicksort while speeding up drastically for many input distributions.

Download Link:

Additional Links:

Subscribe to the Weekly CS Paper Newsletter to get a computer science paper every weekend
No risk. One click unsubscribe.