In my dissertation I analyze a parametric scheme of Quicksort variants with an arbitrary number of pivots. Using the mathematical analysis, I discuss in detail, which choices for parameters look promising.
Generic one-pass multiway partitioning
The parametric partitioning algorithm that I consider
- partitions the input into $s$ segments at once (around $s-1$ pivots),
- chooses these pivots as order statistics from a sample according to the sampling parameter $\mathbf t$,
- works in “one pass” over the array, growing $\lceil m\rceil$ segments from the left and $s-\lfloor m\rfloor$ segments from the right, where $0\le m\le s$ is another parameter.
The analysis covers the average costs of Quicksort with any choice of the above parameters.
Chapter 8 of my dissertation contains an analysis of generic $s$-way Quicksort on inputs with equal elements. I describe some details of the analysis here.
Relation to Other Publications
The analyses in my dissertation build on my papers on YBB Quicksort, in particular Analysis of Pivot Sampling in Dual-Pivot Quicksort, and are an extension thereof.
My analysis of Quicksort with equal keys is an extension of Chapter 8 of my dissertation.
A key idea to fairly compare different $s$-way Quicksort variants is that of entropy-equivalent sampling: Choose one single pivot of the same quality as the $s-1$ pivots chosen according to sampling parameter $\mathbf t$. I found a way to do that for any $\mathbf t$ so that one can exactly simulate the subproblem-shrinking effect of one $s$-way partitioning round by a certain number of binary partitioning rounds.
We can then fairly compare the intrinsic values of a certain partitioning method without having pivots of different quality skewing the picture.
A nice hardcover version is available (for under 40 USD for a nicely printed full-color hardcover book) from IngramSpark, a large print-on-demand publisher. Check here where to buy.