Analysis of Pivot Sampling in Dual-Pivot Quicksort—A Holistic Analysis of Yaroslavskiy’s Partitioning Scheme
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).