QuickXsort: A Fast Sorting Scheme in Theory and Practice

Edelkamp, Stefan, Weiß, Armin and Wild, S ORCID: 0000-0002-6061-9177
(2020) QuickXsort: A Fast Sorting Scheme in Theory and Practice. Algorithmica: an international journal in computer science, 82 (3). pp. 509-588.

[img] Text
quickXsort_journal.pdf - Author Accepted Manuscript

Download (4MB) | Preview


QuickXsortis a highly efficient in-place sequential sorting scheme that mixesHoare’sQuicksortalgorithm with X, where X can be chosen from a wider rangeof other known sorting algorithms, likeHeapsort,InsertionsortandMergesort.Its major advantage is thatQuickXsortcan be in-place even if X is not. In thiswork we provide general transfer theorems expressing the number of comparisonsofQuickXsortin terms of the number of comparisons of X. More specifically,if pivots are chosen as medians of (not too fast) growing size samples, the aver-age number of comparisons ofQuickXsortand X differ only byo(n)-terms. Formedian-of-kpivot selection for some constantk, the difference is a linear term whosecoefficient we compute precisely. For instance, median-of-threeQuickMergesortuses at mostnlgn−0.8358n+O(logn)comparisons. Furthermore, we examine thepossibility of sorting base cases with some other algorithm using even less compar-isons. By doing so the average-case number of comparisons can be reduced down tonlgn−1.4112n+o(n)for a remaining gap of only 0.0315ncomparisons to the knownlower bound (while using onlyO(logn)additional space andO(nlogn)time over-all). Implementations of these sorting strategies show that the algorithms challengewell-established library implementations like Musser’sIntrosort.

Item Type: Article
Uncontrolled Keywords: Sorting, Quicksort, Mergesort, Heapsort, QuickMergesort, QuickHeapsort, Average-case analysis, Recurrence, Continuous master theorem·, Variance, MergeInsertion
Depositing User: Symplectic Admin
Date Deposited: 22 Oct 2019 14:19
Last Modified: 19 Jan 2023 00:21
DOI: 10.1007/s00453-019-00634-0
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3058984