QuickXsort: a fast sorting scheme in theory and practice (Q2292860)

When investigating classical sorting algorithms, \textit{D. Cantone} and \textit{G. Cincotti} proposed in [Theor. Comput. Sci. 285, No. 1, 25--42 (2002; Zbl 1016.68042)] the separation of the data flow from sorting proper. They maintained the pivoting approach from Quicksort, separating the array to be sorted into a left and a right portion, from the sorting of the, say, left part by invoking an algorithm which in turn may be thought to be provided as a parameter. This overall approach is called \textsc{QuickXsort} in the present paper. Elaborating on this idea, one obtains a family of sorting algorithms, for example \textsc{QuickMergesort} or \textsc{QuickHeapsort} (classic Quicksort would be \textsc{QuickQuicksort} in this scheme, of course). The paper under consideration investigates the approach further, focussing on members of the respective families of Mergesort and of Heapsort, and dealing mainly with the average-case analysis of the emanating algorithms, also providing a glimpse at the variance. Within the control framework laid out by Quicksort, one has to consider the determination of the pivot element, so this selection is investigated as well. Of particular interest is the question of transfer of the plug-in algorithms' average behavior to the behavior of the hosting algorithm. The paper illustrates first the variants \textsc{QuickMergesort} and \textsc{QuickHeapsort} before entering into an investigation of transfer theorems. A closer, more detailed look at the performance of the algorithms is given, before the paper goes into a discussion of \textsc{QuickMergesort}, dealing with Insertionsort respectively Mergeinsertion. Experimental results conclude the paper's main body. Seemingly as an afterthought, a separate section detailing the full proofs is given (actually, this is not really an afterthought, it rather helps the authors to maintain the smooth flow of their narrative). The proofs capitalize of course on the basic recursion for the average-case analysis of Quicksort, they make heavy use of some helpful properties Hölder-continuous functions on the unit interval. This rich paper is thoughtfully organized, well written and, given its technial nature, not too difficult to follow. It provides a very careful and detailed mathematical analysis of its topics, indicating also topics for further work. It will reward a careful reading very well.