Quicksort Is Optimal For Many Equal Keys

Abstract

I prove that the average number of comparisons for median-of-$k$ Quicksort (with fat-pivot a.k.a. three-way partitioning) is asymptotically only a constant $\hat{I}{\pm }_k$ times worse than the lower bound for sorting random multisets with $\hat{I}\text{c◯}(n^{\epsilon })$ duplicates of each value (for any $\epsilon >0$). The constant is $\hat{I}{\pm }_k=\ln (2)/(H_{k+1}-H_{(k+1)/2})$, which converges to 1 as $k\to \infty$, so Quicksort is asymptotically optimal for inputs with many duplicates. This resolves a conjecture by Sedgewick and Bentley (1999, 2002) and constitutes the first progress on the analysis of Quicksort with equal elements since Sedgewick's 1977 article.

v4 is a major reorganization of sections; a shortened version appears in the proceedings of ANALCO 2018