Wild, Sebastian ORCID: 0000-0002-6061-9177
(2016)
Quicksort Is Optimal For Many Equal Keys.
.
Text
1608.04906v4.pdf - Submitted version Download (997kB) | Preview |
|
Text
1608.04906v4.pdf - Author Accepted Manuscript Download (997kB) | Preview |
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 $\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.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Additional Information: | v4 is a major reorganization of sections; a shortened version appears in the proceedings of ANALCO 2018 |
Uncontrolled Keywords: | cs.DS, cs.DS, math.PR |
Depositing User: | Symplectic Admin |
Date Deposited: | 21 Oct 2019 15:06 |
Last Modified: | 19 Jan 2023 00:21 |
DOI: | 10.1137/1.9781611975062.2 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3058943 |