 Multiselection by balanced rank partitioning

To find the order statistics at ranks $k,2k,\dots ,n$ when $n/k$ is a power of two, partition into equal lower and upper rank halves and recurse, stopping at blocks of size $k$. Return each leaf block's maximum. Half boundaries are multiples of $k$, so these leaf maxima are exactly the requested ranks. Linear-time selection gives total $\Theta (n)$ partition work per internal level and $\Theta (n)$ leaf work, hence $\Theta (n(1+\log (n/k)))$ overall. The shorter displayed bound applies when $n/k\ge 2$.