Abstract The median, the 0.25‐percentile and the 0.75‐percentile are three of the most relevant ranks in data analysis. MED2Q is a new in situ algorithm to solve this problem. It asymptotically performs an average of 2 5/8 n + o(n) comparisons when n numbers are given as input thus becoming the asymptotically fastest algorithm for this problem reported to date. The performance of MED2Q is compared with those of FIND1 and ALGORITHM 4892, two well‐known selection algorithms adapted to this specific problem. From this performance comparison, MED2Q is best when input sets consist of more than 50,000 numbers.

It is shown that n + k - O (1) comparisons are necessary, on average, to find the k th smallest of n numbers ( k ⪇ n /2). This lower bound matches the behavior of the technique of Floyd and Rivest to within a lower-order term. 7 n /4 ± o ( n ) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of 9 n /4 ± o ( n ) and a lower bound of 2 n - o ( n ) are shown for the max-min-median problem.

We consider problems such as selecting the k-th smallest of n numbers in as few comparisons as possible on average. n + k - 0(1) comparisons are proved to be necessary for this particular problem when k ≤ n/2. This shows a technique of Floyd and Rivest is essentially optimal. 7n/4 = o(n) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of 9n/4 + o(n) and a lower bound of 2n − o(n) are shown for the max-min-median problem.