Order Statistics

Definition The $i$-th order statistic of a set of $n$ elements is

the $i$th smallest element.

• Minimum, maximum, and lower/upper median.
• An algorithm that maintains both max and min requires at most $3\lfloor n/2\rfloor$ comparisons.