An Efficient Algorithm for the Approximate Median Selection Problem

We present an efficient algorithm for the approximate median selection problem. The algorithm works in-place; it is fast and easy to implement. For a large array it returns, with high probability, a very close estimate of the true median. The running time is linear in the length n of the input. The algorithm performs fewer than $$ \frac{4} {3}n $$ comparisons and $$ \frac{1} {3}n $$ exchanges on the average. We present analytical results of the performance of the algorithm, as well as experimental illustrations of its precision.