All Publications

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

Jan 2019 (Written: Jun 2018)

Conrado Martínez, Markus Nebel, and Sebastian Wild:

Meeting on Analytic Algorithmics and Combinatorics 2019
in M. Mishna and J.I. Munro (Eds.): ANALCO 2019, SIAM, pp 54–66

| read herePDFDOI arXivslides |

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.