Quicksort is optimal for many equal keys

Wild, S ORCID: 0000-0002-6061-9177 (2018) 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 α<inf>k</inf> times worse than the lower bound for sorting random multisets of n elements with Ω(n^ε) duplicates of each value (for any ε > 0). The constant is α<inf>k</inf> = ln(2)/H<inf>k</inf>+1 − H<inf>(</inf>k+1)/<inf>2</inf>, which converges to 1 as k → ∞, 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.

Item Type:	Conference 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:	22 Apr 2026 10:58
DOI:	10.1137/1.9781611975062.2
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3058943
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.