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

This paper considers the potential of multiway partitioning in Quickselect.

Unlike for sorting, producing many segments is not necessarily helpful in selecting order statistics, but with small samples, using two pivots reduces the amount of memory transfers.

We analyze two scenarios (that require different analytical tools):

1. The sought rank is random.
2. The sought rank is $\alpha n$ for a fixed $\alpha\in(0,1)$.

In the first scenario, the distributional master theorem developed in my dissertation can be used to obtain expected costs for a generic version of Quickselect.

For the linear ranks, we obtain a recurrence in $n$ and $\alpha$ that in general seems too hard to solve. An asymptotic approximation is possible by solving an integral equation. We give the first elementary proof that the solution of this equation is indeed an asymptotic solution of the bivariate recurrence.