Selecting the median and two quartiles in a set of numbers
Walter Cunto, J. Ian Munro, Manuel Rey · Software Practice and Experience · 1992
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.