Abstract:
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.