A random algorithm for multiselection

Given a set $S$ of $n$ elements drawn from a linearly ordered set and a set $K=\{k_1,k_2,\ldots,k_r\}$ of positive integers between 1 and $n$, the multiselection problem is to select the $k_i$th smallest element for all values of $i$, $1\le i\le r$. We present an efficient randomised algorithm to solve this problem in time $O(n\ln r)$ with probability at least $1-cn^{-1}$, where $c$ is a positive constant.