Computing the maximum and the median
Edward M. Reingold · 1971
This note is concerned with the number of binary comparisons required to compute the maximum or the median of sets of numbers. The new results are: (a) the maximum of a set of n integers cannot be computed in fewer than n-1 comparisons if comparisons of only linear functions of the integers are permitted, but the maximum can be computed in log2 n comparisons if comparisons can be made between exponential functions of the integers and (b) the median of a set of n integers can be computed using only 2n comparisons if comparisons between polynomial functions of the integers are permitted.