Order Statistics and Median

Overview

The $i$-th order statistic of a set of $n$ elements is the $i$-th smallest element. The minimum is the 1st order statistic ($i = 1$); the maximum is the $n$-th; the median (lower median) is the $\lfloor (n+1)/2 \rfloor$-th.

The selection problem: given a set $A$ of $n$ distinct numbers and an integer $i$ where $1 \le i \le n$, find the element larger than exactly $i-1$ others.

Finding Minimum and Maximum

A simple linear scan finds the minimum (or maximum) in $n-1$ comparisons:

min = A[1]
for j = 2 to n:
    if A[j] < min: min = A[j]

Finding both minimum and maximum simultaneously can be done in $\lceil 3n/2 \rceil - 2$ comparisons: process elements in pairs, compare within each pair, then compare the larger against the running maximum and the smaller against the running minimum.

Task	Comparisons
Find min only	$n - 1$
Find max only	$n - 1$
Find min and max naively	$2n - 2$
Find min and max optimally	$\lceil 3n/2 \rceil - 2$

Quickselect

Quickselect uses the same partition subroutine as quicksort, but only recurses on the side containing the desired order statistic:

1. Call PARTITION(A, p, r) which rearranges A[p..r] around a pivot and returns pivot index $q$.
2. Let $k = q - p + 1$ (the rank of the pivot within the subarray).
3. If $i = k$, return A[q] — the pivot is the answer.
4. If $i < k$, recurse on A[p..q-1] for the $i$-th statistic.
5. If $i > k$, recurse on A[q+1..r] for the $(i-k)$-th statistic.

Complexity

• Expected: $\Theta(n)$. Each partition is $\Theta(m)$ on a subarray of size $m$, but the subarray shrinks by a constant factor in expectation.
• Worst case: $\Theta(n^2)$, when the pivot is always the minimum or maximum (e.g. already-sorted or reverse-sorted input).

Improvements

1. Randomised pivot: Choose the pivot at random; makes worst-case inputs unlikely.
2. Median-of-three: Pick three elements, use their median as pivot. Guarantees at least one element on each side, reducing the worst-case probability from $\sim 2/n$ to $\sim 2/n^2$.
3. Three-way partition: Split into $<$ pivot, $=$ pivot, $>$ pivot. Excellent when many duplicates exist.

Median-of-Medians (Blum-Floyd-Pratt-Rivest-Tarjan)

This deterministic algorithm finds the $i$-th order statistic in $O(n)$ worst-case time:

1. Divide the $n$ elements into groups of 5. Find the median of each group (constant-time per group via insertion sort on 5 elements).
2. Recursively find the median of these $\lceil n/5 \rceil$ medians; use it as the pivot.
3. Partition around this median-of-medians pivot.
4. Recurse on the appropriate side.

Why $O(n)$: At least $3(\lceil \frac{1}{2} \lceil n/5 \rceil \rceil - 2) \ge 3n/10 - 6$ elements are guaranteed to be greater than the pivot, and symmetrically for less than. So even the larger side is at most $7n/10 + 6$ elements. The recurrence:

$T(n) = T(\lceil n/5 \rceil) + T(7n/10 + 6) + \Theta(n) = O(n)$

For $n \ge 140$, the constant factor works out; for smaller $n$, any constant-time method suffices.

Practical Considerations

For most applications, simply sorting the array in $\Theta(n \log n)$ and reading the $i$-th element is fast enough and far simpler to implement. Quickselect (randomised) is used in practice when $n$ is large and sorting overhead is undesirable.

Summary

Method	Time (expected)	Time (worst case)
Sort then pick $i$-th	$\Theta(n \log n)$	$\Theta(n \log n)$
Quickselect (randomised)	$\Theta(n)$	$\Theta(n^2)$
Median-of-medians	$\Theta(n)$	$\Theta(n)$
Find min or max	$\Theta(n)$	$\Theta(n)$
Find min and max	$\Theta(n)$	$\Theta(n)$