# 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.

## 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.

## 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.