# Analysis of Branch Misses in Quicksort

Jan 2015 (Written: Aug 2014)

Conrado Martínez, Markus Nebel, Sebastian Wild:

Meeting on Analytic Algorithmics and Combinatorics 2015
in Y. Azar and H. Bast and G. Herman (Eds.): ESA 2018, LIPIcs 112, Dagstuhl, 2018, 63:1-63:16 pp 114–128

In fact, the overall result is that median-of-$k$ Quicksort incurs more branch misses the larger $k$ gets.
In my dissertation, I sketch how to extend the analysis of this paper to generic $s$-way one-pass partitioning, and also give a rigorous proof that we can safely use the steady state of the predictor automaton to determine expected branch-miss counts.