= Multiselection by balanced rank partitioning
{title2=$\Theta(n\log(n/k))$}
To find the order statistics at ranks $k,2k,\ldots,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\geq2$.
Back to article page
