  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 $\alpha_k$ times worse than the lower bound for sorting random
multisets with $\Omega(n^\varepsilon)$ duplicates of each value (for any
$\varepsilon>0$). The constant is $\alpha_k = \ln(2) /
\bigl(H_{k+1}-H_{(k+1)/2} \bigr)$, 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.
