QuickXsort – A Fast Sorting Scheme in Theory and Practice

QuickXsort is a scheme for turning many non-inplace sorting methods X into a constant-extra-space sorting method with almost the same number of comparisons. The idea is explained in detail on the site for my AofA paper on QuickXsort.

In this paper, we extend the refined analysis to median-of-$k$ QuickXsort for sample sizes $k = k(n)$ that grow with $n$, and we simplify my analysis for fixed $k$.

Moreover, we give a transfer theorem for the variance of QuickXsort, and we consider Mergesort with more comparison-efficient methods as base case as X.

Finally, we include an extensive running-time study comparing different QuickMergesort variants to other efficient sorting methods. When sorting integers, classic Quicksort remains in the lead, but QuickMergesort is only 5% slower. When comparisons are slightly more expensive (emulated by computing log before the comparisons), QuickMergesort is fastest.