⬑ All Publications

Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential

Oct 2016 (Written: Apr 2016)

Sebastian Wild:

Doktorarbeit (Ph.D. Thesis), Department of Computer Science, Technische Universität Kaiserslautern

| pdf | urn | ISBN | slides |

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.

book cover book cover
Front and back cover of the printed version of my dissertation.

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.
partitioning invariant
Invariant for generalized one-pass partitioning. Initially, the “?-area” covers the whole array; partitioning is finished, when it has been consumed completely. The $k_i$-indices are initially equal to $\mathit{left}$, and all $g_j$-indices are initially $\mathit{right}$; partitioning is finished when $k$ and $g$ have met.

The analysis covers the average costs of Quicksort with any choice of the above parameters.

Equal Keys

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.

Entropy-Equivalent Sampling

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.

This idea is explained in the slides linked above from my defense talk. A second set of slides from a more comprehensive 1h-talk about the topic is also available.

Printed Version

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.