Pattern-defeating Quicksort

Abstract

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.

20 pages, 10 figures

References in corpus (1)

• Quicksort with median of medians is considered practical

Cited by in corpus (1)

• LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization