Analysis of Pivot Sampling in Dual-Pivot Quicksort—A Holistic Analysis of Yaroslavskiy’s Partitioning Scheme

Aug 2016 (Written: Oct 2014)

Markus Nebel, Sebastian Wild, and Conrado Martínez:

Algorithmica 75, 4, pp 632–683 (Aug 2016)

This article gives the broadest analysis of dual-pivot Quicksort (YBB Quicksort) found in the literature, covering

pivot sampling, i.e., choosing pivots from a sample,
an Insertionsort cutoff,
and several different cost measures.

We discuss in detail that only scanned elements explain the better running time observed for dual-pivot Quicksort compared to classic single-pivot Quicksort. Scanned elements approximate the amount of data transfered from main memory and are thus related to cache misses.

Relation to Other Papers

This is the full version of the AofA conference paper.

I also gave a talk in Dagstuhl about the results (with less of a focus on the analytical details).