Medians and Order Statistics

By the end of this lesson you will be able to find the smallest and largest elements of a list in the fewest possible comparisons, find "the k-th smallest thing" in expected linear time with randomized selection (randomizedSelect), find it in guaranteed worst-case linear time with the median-of-medians algorithm (select) — and understand exactly how these algorithms dodge the Ω(n lg n) wall that full sorting can never get under, by never fully sorting anything.

1. Order statistics & the selection problem

For a set of n distinct numbers, the i-th order statistic is simply the i-th smallest value. The 1st order statistic is the minimum; the n-th order statistic is the maximum. The median is the "middle" value: when n is odd there is one unique median at position (n+1)/2; when n is even there are technically two "middle" elements (at positions n/2 and n/2+1) and this lesson's convention is that "the median" means the lower median, at position ⌊(n+1)/2⌋.

The selection problem: given a list a of n (distinct) numbers and an index i with 1 ≤ i ≤ n, find the element of A that is larger than exactly i − 1 other elements — i.e. the i-th smallest.

The obvious solution is: sort a (Θ(n lg n) with merge sort or heapsort), then read off sorted[i - 1]. This chapter's whole point is that you can do much better because you don't need the full ranking — only one position in it. Every algorithm here squeezes out extra speed by throwing away large chunks of the input that provably cannot contain the answer, without ever sorting those chunks.

The definitions as Dart

Ranks count from 1 ("1st smallest"), Dart lists count from 0: the i-th smallest is sorted[i - 1]. The two median positions for n elements are (n+1)/2 when n is odd, and n/2 (lower) and n/2 + 1 (upper) when n is even — medianPositions returns them as a record.

The selection problem as a literal definition — “larger than exactly i − 1 others” — is an O(n²) brute force; the rest of this lesson is about doing it in O(n).

Input size → what is feasible: n ≤ 10³ → even this quadratic definition is instant (10⁶ steps); n = 10⁵ → sort (n lg n ≈ 1.7·10⁶); n ≥ 10⁷ → you need the linear-time algorithms below.

2. Minimum and maximum

minimum(a) keeps a running champion and compares every other element against it once:

The same scan as numbered pseudocode (0-indexed, exactly like the Dart below):

minimum(a): the smallest value of a, n = a.length
1  min ← a[0]
2  for i from 1 to n − 1:
3      if min > a[i]:
4          min ← a[i]
5  return min

This makes exactly n − 1 comparisons. Is that provably the fewest possible? Yes: picture a single-elimination tournament where "losing" means "being found to not be the minimum". Every element except the true minimum must lose at least once to something (directly or transitively) — that requires at least n − 1 "loss" comparisons overall, so n − 1 is both achievable and optimal. MAXIMUM is the mirror image, also n − 1 comparisons.

Edge case: what happens on the smallest possible input, a single element?

Try your own array (any length, any integers):

int minimum(List<int> a) {
  var min = a[0];
  for (var i = 1; i < a.length; i++) {
    if (min > a[i]) min = a[i];
  }
  return min;
}

MAXIMUM is the mirror image (flip the comparison):

The claim “exactly n − 1 comparisons” as code — count them with a counter, and count the losers to see why n − 1 is also a lower bound (every element except the minimum must lose at least once):

Input size → what is feasible: n ≤ 10⁷ → one MINIMUM scan is about 10⁷ steps (< 0.1 s); sorting just to read a[0] would cost n lg n ≈ 2.3·10⁸. Values are Dart 64-bit int, so the comparison never overflows.

Now the more interesting question: what if you need both the minimum AND the maximum? Doing MINIMUM then MAXIMUM separately costs 2(n − 1) comparisons. you can do noticeably better — at most 3⌊n/2⌋ — by processing elements in pairs: compare the two members of a pair against each other first (1 comparison), then only compare the pair's smaller member against the running min, and the pair's larger member against the running max (2 more comparisons) — 3 comparisons per 2 elements instead of 4.

The pairing method as numbered pseudocode (0-indexed):

simultaneousMinMax(a): both extremes, 3 comparisons per pair of elements
1  n ← a.length
2  if n is odd:
3      min ← a[0]; max ← a[0]; start ← 1        // free: no comparison needed
4  else:
5      order a[0], a[1] into min and max; start ← 2   // 1 comparison
6  for i from start to n − 2, step 2:
7      order a[i], a[i + 1] into small and large       // 1 comparison
8      if small < min: min ← small                    // 1 comparison
9      if large > max: max ← large                    // 1 comparison
10 return (min, max)

(int, int) simultaneousMinMax(List<int> a) {
  final n = a.length;
  int min, max, start;
  if (n.isOdd) {
    min = max = a[0];
    start = 1;
  } else {
    if (a[0] <= a[1]) {
      min = a[0];
      max = a[1];
    } else {
      min = a[1];
      max = a[0];
    }
    start = 2;
  }
  for (var idx = start; idx < n; idx += 2) {
    final x = a[idx], y = a[idx + 1];
    int small, large;
    if (x <= y) {
      small = x;
      large = y;
    } else {
      small = y;
      large = x;
    }
    if (small < min) min = small;
    if (large > max) max = large;
  }
  return (min, max);
}

The counts as code: the same control flow with a comparison counter. The exact number is ⌈3n/2⌉ − 2 (which is ≤ 3⌊n/2⌋, the usual bound), against 2n − 2 for the naive version:

Input size → what is feasible: n ≤ 10⁷ → the naive 2n − 2 ≈ 2·10⁷ comparisons is fine on plain ints; use the pairing method (≈ 1.5·10⁷) when a comparison is expensive (strings, network calls).

Edge case: an even-length array where every value is identical — the pairing trick must still terminate cleanly with min = max:

Try your own array (odd or even length):

Runner-up of a knockout (find the 2nd smallest in at most n + ⌈lg n⌉ − 2 comparisons). Run a single-elimination tournament in which every match keeps the smaller value, and make each player remember the values it has beaten directly. The champion is the minimum and costs n − 1 matches. Now the key observation: the 2nd smallest element can only ever have lost to the minimum, because anyone else it met was larger and would have lost to it. So it is among the values the champion beat directly. The champion plays at most ⌈lg n⌉ matches (one per round), so it beat at most ⌈lg n⌉ values, and finding the smallest of those takes at most ⌈lg n⌉ − 1 more comparisons. Total: (n − 1) + (⌈lg n⌉ − 1) = n + ⌈lg n⌉ − 2. The code below is checked in verify/c09.dart.

The knockout runner-up as code — the tournament with a comparison counter (n − 1 matches, then (number of opponents the champion beat) − 1 more to find the best of them; the champion plays at most ⌈lg n⌉ matches):

Input size → what is feasible: 2 ≤ n ≤ 10⁵ distinct values → about n + 17 − 2 = 100,015 comparisons; two full passes would also be O(n) — the tournament matters when comparisons are expensive.

3. randomizedSelect: expected linear time

randomizedSelect reuses partition from quicksort, but with one crucial difference from quicksort: after partitioning, it recurses into only one side — the side that must contain the answer — instead of both sides. That one change is what turns an Θ(n lg n) sorting algorithm into an expected Θ(n) selection algorithm.

partition(a, p, r): Lomuto split around the pivot a[r]; returns the pivot's final index
1  pivot ← a[r]
2  i ← p − 1                         // a[p..i] holds the values ≤ pivot seen so far
3  for j from p to r − 1:
4      if a[j] ≤ pivot:
5          i ← i + 1
6          swap a[i], a[j]
7  swap a[i + 1], a[r]               // drop the pivot between the two groups
8  return i + 1

randomizedPartition(a, p, r): partition around a uniformly random pivot
1  m ← random integer in [p, r]
2  swap a[m], a[r]
3  return partition(a, p, r)

randomizedSelect(a, p, r, i): the i-th smallest of a[p..r]   (i = 1 is the minimum)
1  if p = r:
2      return a[p]
3  q ← randomizedPartition(a, p, r)
4  k ← q − p + 1                     // the pivot is the k-th smallest of a[p..r]
5  if i = k:
6      return a[q]
7  if i < k:
8      return randomizedSelect(a, p, q − 1, i)
9  return randomizedSelect(a, q + 1, r, i − k)

A normal-case trace, seeded so it's reproducible — watch how, unlike quicksort, only ONE side ever gets recursed into:

Try your own array and rank (values must be distinct integers; keep n ≤ 14 so the array stays readable). Format: values | i=rank.

Now the edge/worst case: what if the "random" pivot is unlucky every single time, e.g. an already-ascending array where the chosen pivot always happens to be the current largest element?

int _lomutoPartition(List<int> a, int p, int r) {
  final x = a[r];
  var i = p - 1;
  for (var j = p; j <= r - 1; j++) {
    if (a[j] <= x) {
      i++;
      final t = a[i];
      a[i] = a[j];
      a[j] = t;
    }
  }
  final t = a[i + 1];
  a[i + 1] = a[r];
  a[r] = t;
  return i + 1;
}

int _randomizedPartition(List<int> a, int p, int r, math.Random rng) {
  final i = p + rng.nextInt(r - p + 1);
  final t = a[i];
  a[i] = a[r];
  a[r] = t;
  return _lomutoPartition(a, p, r);
}

int randomizedSelect(List<int> a, int p, int r, int i, math.Random rng) {
  if (p == r) return a[p];
  final q = _randomizedPartition(a, p, r, rng);
  final k = q - p + 1;
  if (i == k) return a[q];
  if (i < k) return randomizedSelect(a, p, q - 1, i, rng);
  return randomizedSelect(a, q + 1, r, i - k, rng);
}

The two claims about this algorithm as code. Worst case: with the pivot always the last element of an ascending array, every round removes just one element, so the comparisons are (n−1) + (n−2) + … + 1 = n(n−1)/2 — for n = 100 that is 4950. Typical case: the same loop with a random pivot averages about 3.4n comparisons for the median:

Input size → what is feasible: n ≤ 10³ → anything works; n = 10⁷ distinct values → randomizedSelect does about 3.4·10⁷ comparisons while sorting needs about 2.3·10⁸; with many duplicates use a three-way partition (Lomuto’s ≤ degrades to n²).

Why is the expected time linear? Define an indicator random variable X_k = 1 if the subarray a[p..q] (the low side plus the pivot) has exactly k elements, for k = 1, …, n. Since the pivot is uniformly random, Pr{X_k = 1} = 1/n for every k, so E[X_k] = 1/n. When X_k = 1 the two possible recursive calls have sizes k−1 (low side) and n−k (high side). This gives a recurrence T(n) ≤ Σ X_k · T(max(k−1, n−k)) + O(n); taking expectations (and using that the recursive call size doesn't depend on future randomness) leads to E[T(n)] ≤ (2/n) Σ_{k=⌊n/2⌋}^{n−1} E[T(k)] + O(n) (as k runs over 1, …, n, the value max(k−1, n−k) lands in the range ⌊n/2⌋, …, n−1, hitting every value in ⌈n/2⌉, …, n−1 twice and ⌊n/2⌋ once when n is odd, which is where the factor of 2 comes from). A substitution proof (guess E[T(n)] ≤ cn, verify the recurrence holds) confirms E[T(n)] = O(n) — so expected Θ(n), even though any single run could get unlucky.

The indicator-variable argument in code. First, Pr{Xk = 1} = 1/n: a seeded histogram of where the random pivot lands. Second, the recurrence E[T(n)] = n + (1/n)·Σk=0n−1 E[T(max(k, n−1−k))] evaluated exactly and checked against the bound E[T(n)] ≤ 4n (the ratio creeps up toward 4 from below):

4. select: worst-case linear time

SELECT guarantees Θ(n) worst-case time by replacing the random pivot with a carefully engineered one: the median of medians. It works in five steps, written here as one listing:

select(a, p, r, i): the i-th smallest of a[p..r], worst-case linear
1  if r − p + 1 ≤ 5: sort a[p..r] and return its i-th smallest        // base case
2  cut a[p..r] into groups of 5 (the last may be shorter); medians ← each group's median
3  x ← select(medians, 0, medians.length − 1, ⌈medians.length / 2⌉)   // median of medians
4  q ← partitionAround(a, p, r, x);  k ← q − p + 1                    // x lands at index q
5  if i = k: return x
   if i < k: return select(a, p, q − 1, i)
   else: return select(a, q + 1, r, i − k)

Watch the groups of 5, their medians, the median-of-medians pivot, and the partition + discarded region, all computed live from the array below. (A slice of at most 5 elements is simply insertion-sorted and read off, which is what line 2 does to every group anyway.)

Try your own array and rank (distinct integers, n ≤ 40). Format: values | i=rank.

Edge case: a larger input (n = 27) where even the ⌈n/5⌉ = 6 group-medians is itself > 5 elements, forcing a second level of recursion just to find the median of medians:

List<int> _insertionSort(List<int> a) {
  final b = List<int>.from(a);
  for (var j = 1; j < b.length; j++) {
    final key = b[j];
    var k = j - 1;
    while (k >= 0 && b[k] > key) {
      b[k + 1] = b[k];
      k--;
    }
    b[k + 1] = key;
  }
  return b;
}

int _medianOfSmallGroup(List<int> g) {
  final s = _insertionSort(g);
  return s[(s.length - 1) ~/ 2]; // lower median (this lesson's convention)
}

int _partitionAroundValue(List<int> a, int p, int r, int xVal) {
  var idx = p;
  while (a[idx] != xVal) {
    idx++;
  }
  final t = a[idx];
  a[idx] = a[r];
  a[r] = t;
  return _lomutoPartition(a, p, r);
}

int select(List<int> a, int p, int r, int i) {
  final n = r - p + 1;
  if (n <= 5) {
    final sorted = _insertionSort(a.sublist(p, r + 1));
    for (var k = 0; k < sorted.length; k++) {
      a[p + k] = sorted[k];
    }
    return sorted[i - 1];
  }
  final medians = <int>[];
  for (var g = p; g <= r; g += 5) {
    medians.add(_medianOfSmallGroup(a.sublist(g, math.min(g + 5, r + 1))));
  }
  final x = select(medians, 0, medians.length - 1, (medians.length / 2).ceil());
  final q = _partitionAroundValue(a, p, r, x);
  final k = q - p + 1;
  if (i == k) return a[q];
  if (i < k) return select(a, p, q - 1, i);
  return select(a, q + 1, r, i - k);
}

Steps 1–2 and the “at least 3n/10 − 6” count as code. groupMedians returns the ⌈n/5⌉ medians; guaranteedDiscard(n) is the count 3(⌈½⌈n/5⌉⌉ − 2) of elements strictly on each side of the median-of-medians x, and countsAroundMedianOfMedians measures the real counts on a concrete array so you can see they are never smaller. Since that count is at least 3n/10 − 6, the larger side has at most n − (3n/10 − 6) = 7n/10 + 6 elements:

Input size → what is feasible: n ≤ 10⁵ → SELECT is instant but its constant is large (a larger constant than randomizedSelect’s 3.4n); n = 10⁷ adversarial input → SELECT or introselect, never plain last-element pivots.

Why is this worst-case Θ(n)? Arrange the ⌈n/5⌉ group medians in sorted order around x. At least half of those groups (minus the one possibly-short leftover group, and minus x's own group) contribute 3 elements each that are provably ≥ x (their own median and the 2 group members ≥ that median) — counting those elements shows at least (3/10)n − 6 elements are ≥ x, and symmetrically at least (3/10)n − 6 are ≤ x. So step 5 never recurses on more than 7n/10 + 6 elements.

A substitution proof — guess T(n) ≤ cn for a large enough constant c — plugs into the recurrence and, using n/(n−70) ≤ 2 once n ≥ 140, shows the guess holds whenever c ≥ 20a (where a is the constant hidden in the O(n) term). The two fractions 1/5 and 7/10 sum to 9/10 < 1, which is exactly what makes the recursion's total work geometrically shrink instead of blowing up — this is the same shape of argument as the recursion-tree intuition from the recurrences lesson, just applied to two different-sized recursive calls instead of two equal ones.

The recurrence as code: T(n) ≤ T(⌈n/5⌉) + T(7n/10 + 6) + n (the hidden constant a is 1, and T(n) = n below 140), evaluated bottom-up. The check T(n) ≤ 20n is the substitution result c ≥ 20a; the fractions 1/5 + 7/10 = 9/10 < 1 are why the ratio T(n)/n flattens out (its limit is 1/(1 − 9/10) = 10):

The group-size experiment as code: the same recurrence for groups of size g, where each group whose median is on the far side contributes ⌈g/2⌉ guaranteed elements. For g = 3 the fractions are 1/3 + 2/3 = 1 and T(n)/n grows by a constant at every decade of n (that is n lg n); for g = 5 (9/10) and g = 9 (5/6) it levels off at 10 and 6:

5. Weighted median

Formally: given values x_1, …, x_n with positive weights w_1, …, w_n summing to 1, the weighted median is the x_k such that Σ_{x_i < x_k} w_i < 1/2 and Σ_{x_i > x_k} w_i ≤ 1/2. Setting every w_i = 1/n recovers the ordinary median.

The definition as a checker: isWeightedMedian sums the weight strictly left and strictly right of xs[k] and tests left < total/2 and right ≤ total/2 (the weights are compared with their own total, so they need not sum to 1):

Input size → what is feasible: n ≤ 10⁵ distinct values → the select-pivot version below does about 2·(n + n/2 + n/4 + …) work; the sort-and-scan alternative is n lg n ≈ 1.7·10⁶ — fine, but a linear-time method is the goal here.

Edge case: a single remaining candidate needs no comparisons at all — it's trivially the weighted median:

Try your own values and weights (weights need not sum to exactly 1 — they get normalized against their own total). Format: values | w=weights.

int weightedMedian(List<int> xs, List<double> ws) {
  final total = ws.fold<double>(0, (s, w) => s + w);
  var x = List<int>.from(xs);
  var w = List<double>.from(ws);
  var loWeight = 0.0;
  while (true) {
    if (x.length == 1) return x[0];
    final pivot = selectKth(x, (x.length + 1) ~/ 2);
    final less = <int>[], lessW = <double>[];
    final eq = <int>[], eqW = <double>[];
    final more = <int>[], moreW = <double>[];
    for (var idx = 0; idx < x.length; idx++) {
      if (x[idx] < pivot) {
        less.add(x[idx]);
        lessW.add(w[idx]);
      } else if (x[idx] > pivot) {
        more.add(x[idx]);
        moreW.add(w[idx]);
      } else {
        eq.add(x[idx]);
        eqW.add(w[idx]);
      }
    }
    final wLess = lessW.fold<double>(0, (s, v) => s + v);
    final wEq = eqW.fold<double>(0, (s, v) => s + v);
    if (loWeight + wLess >= total / 2 && wLess > 0) {
      x = less;
      w = lessW;
    } else if (loWeight + wLess + wEq >= total / 2) {
      return pivot;
    } else {
      loWeight += wLess + wEq;
      x = more;
      w = moreW;
    }
  }
}

Two elegant consequences: (1) the 1-D depot location problem — minimizing Σ w_i |p − x_i| over the choice of point p — is solved exactly by the weighted median. (2) The 2-D version with Manhattan distance (|x−x_i| + |y−y_i|) separates cleanly into two independent 1-D problems: the optimal x-coordinate is the weighted median of all the x-coordinates, and the optimal y-coordinate is the weighted median of all the y-coordinates, computed completely independently of each other.

Both consequences as code: the depot cost Σ wi·|p − xi| and the Manhattan cost as a sum of an x-part and a y-part, so the x and y coordinates can be optimised independently (checked against a brute-force grid in the verify file):

6. Correctness & running time, side by side

Loop invariant for minimum (three parts): at the start of each iteration of the for loop, min holds the smallest value among a[0..i-1].

• Initialization: before the first iteration (i = 1), min = a[0], which is trivially the smallest of the 1-element range a[0..0].
• Maintenance: each iteration compares min to a[i] and keeps whichever is smaller, so after the body runs, min is the smallest of a[0..i] — exactly what's needed for the invariant to hold at the start of the next iteration.
• Termination: the loop ends when i reaches a.length = n, so the invariant (now covering a[0..n-1]) says min is the smallest of the entire array — which is exactly correctness.

partition's own loop invariant (from the quicksort lesson — reused unchanged inside both randomizedSelect and select) guarantees that after it finishes, every element in a[p..q-1] is ≤ the pivot and every element in a[q+1..r] is > the pivot — which is exactly why it's safe for randomizedSelect / SELECT to discard one whole side: the invariant is what proves the discarded side truly cannot contain the i-th smallest.

Both invariants as code. MINIMUM’s invariant is asserted at the top of every iteration (the already-scanned prefix a[0..i-1]); partition’s postcondition is what makes it safe to throw away one side:

Quiz

Interview questions

Cheat sheet