Average Cost of QuickXsort with Pivot Sampling

Wild, Sebastian ORCID: 0000-0002-6061-9177 (2018) Average Cost of QuickXsort with Pivot Sampling. .

Access the full-text of this item by clicking on the Open Access link.

Text
1803.05948v2.pdf - Submitted version
Download (753kB) | Preview

Official URL: http://dx.doi.org/10.4230/lipics.aofa.2018.36

Abstract

QuickXsort is a strategy to combine Quicksort with another sorting method X, so that the result has essentially the same comparison cost as X in isolation, but sorts in place even when X requires a linear-size buffer. We solve the recurrence for QuickXsort precisely up to the linear term including the optimization to choose pivots from a sample of k elements. This allows to immediately obtain overall average costs using only the average costs of sorting method X (as if run in isolation). We thereby extend and greatly simplify the analysis of QuickHeapsort and QuickMergesort with practically efficient pivot selection, and give the first tight upper bounds including the linear term for such methods.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	updated to final version accepted for AofA 2018
Uncontrolled Keywords:	cs.DS, cs.DS
Depositing User:	Symplectic Admin
Date Deposited:	21 Oct 2019 15:08
Last Modified:	19 Jan 2023 00:21
DOI:	10.4230/LIPIcs.AofA.2018.36
Open Access URL:	http://drops.dagstuhl.de/opus/volltexte/2018/8929/...
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3058942