Adaptive sampling for quickselect

Quickselect with median-of-3 is largely used in practice and its behavior is fairly well understood. However, the following natural adaptive variant, which we call proportion-from-3, had not been previously analyzed: choose as pivot the smallest of the sample if the rank of the sought element is small, the largest if the rank is large, and the median if the rank is medium". We first analyze proportion-from-2 and then proportion-from3. We also analyze ν-find, a generalization of proportion-from-3 with interval breakpoints at ν and 1 -- ν. We show that there exists an optimal value of ν and we also provide the range of values of ν where ν-find outperforms median-of-3. Our results atrongly suggest that a suitable implementation of this variant could be the method of choice in a practical setting. Finally, we also show that proportion-from-s and similar strategies are optimal when s → ∞