Sesquickselect: One and a half pivots for cache-efficient selection

Conrado Martínez, Markus Nebel, Sebastian Wild

Because of unmatched improvements in CPU performance, memory transfers have become a bottleneck of program execution. As discovered in recent years, this also affects sorting in in…