학술논문
Quicksort is optimal for many equal keys.
Document Type
Proceedings Paper
Author
Wild, Sebastian (3-WTRL-SC) AMS Author Profile
Source
Subject
05 Combinatorics -- 05A Enumerative combinatorics
05A16Asymptotic enumeration
05A16
Language
English
Abstract
Summary: ``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 of $n$ elements with $\Omega(n ^\varepsilon)$ duplicates of each value (for any $\varepsilon>0$). The constant is $\alpha_k=\ln(2)/(H_{k+1}-H_{(k+1)/2})$, which converges to 1 as $k\to\infty$, so median-of-$k$ Quicksort is asymptotically optimal for inputs with many duplicates. This partially 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.''