Quicksort is optimal for many equal keys

DOI10.1137/1.9781611975062.2MaRDI QIDQ5195100zbMATH OpenOpenAlexFDO

Authors Sebastian Wild

Publication date 18 September 2019

Published in 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.04906

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms (68W40)

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 $alph{a}_k$ times worse than the lower bound for sorting random multisets with $Omega(n^{v}arepsilon)$ duplicates of each value (for any $varepsilon>0$). The constant is $$, which converges to 1 as $koinfty$, 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.

Recommendations

• Quicksort for Equal Keys
• How good is multi-pivot quicksort?
• Optimal Partitioning for Dual Pivot Quicksort
• How Many Comparisons Does Quicksort Use?
• Optimal sampling strategies for quicksort

Cited in

(5)

• QuickXsort: a fast sorting scheme in theory and practice
• Quicksort for Equal Keys
• Optimal sampling strategies for quicksort
• Nearly-optimal mergesorts: fast, practical sorting methods that optimally adapt to existing runs
• Improving multikey Quicksort for sorting strings with many equal elements

This page was built for publication: Quicksort is optimal for many equal keys

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5195100)