Randomized selection revisited

Krzysztof C. Kiwiel

We show that several versions of Floyd and Rivest's algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min \{k,n-k\}+o(n)$ comparisons on average an…