2026-07-20T09:02:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8929 2024-03-06T10:43:46Z ddc:004 open_access

Average Cost of QuickXsort with Pivot Sampling Wild, Sebastian in-situ sorting constant-factor optimal sorting pivot sampling QuickMergesort QuickHeapsort Quicksort recurrence average-case analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Wild 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.36 urn:nbn:de:0030-drops-89295 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.36 eng https://creativecommons.org/licenses/by/3.0/legalcode