# Pattern-defeating Quicksort

arXiv: https://arxiv.org/abs/2106.05123 · HTML: https://mlsanity.com/paper/2106.05123/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2021.

## Built on by (most cited first, 1 of 1)

- [LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization](https://mlsanity.com/paper/2307.08637/) (2023)

## Abstract (arXiv)

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.