Pivot Sampling in Dual-Pivot Quicksort—Exploiting Asymmetries in Yaroslavskiy’s Partitioning Scheme

Jun 2014 (Written: Jan 2014)

Markus Nebel and Sebastian Wild:

International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) 2014
in Bousquet-Mélou M., Soria M. (eds.): DMTCS-HAL Proceedings Series, vol. BA, pp 325–338

In this paper, we analyze the influence of pivot sampling in dual-pivot Quicksort. This conference paper is superseded by an extended journal version with Conrado Martínez.

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