Linear time selection — median of medians algorithm

WHAT are we even solving?

WHY not just sort? Sorting gives all order statistics but costs $O(n\log n)$. We only need one. Doing more work than necessary is the thing 80/20 tells us to avoid — so we aim for $O(n)$.

HOW Quickselect works (the foundation)

Quickselect = Quicksort that only recurses into the side containing $k$.

1. Pick a pivot $p$.
2. Partition $A$ around $p$: smaller elements left, larger right. Pivot lands at its final sorted index $i$.
3. If $i = k$ → done. If $k < i$ → recurse left. If $k > i$ → recurse right (adjust $k$).

The trick: Median of Medians chooses the pivot

WHY 5? It's the smallest odd group size for which the recursion math closes (gives linear time). We'll see exactly where 5 comes from in the derivation. (Groups of 3 fail; 7 also works but 5 is optimal in practice.)

WHY this pivot is provably good (the heart)

Let $M$ be the median of the $\lceil n/5\rceil$ group-medians. We bound how many elements are guaranteed smaller than $M$ (and by symmetry, larger).

By symmetry, at least $\frac{3n}{10}$ elements are $\ge M$. Therefore the larger side of the partition has at most $n - \frac{3n}{10} = \frac{7n}{10}$ elements.

Worked example 1 — finding the pivot $M$

Array (n=15): [12, 3, 5, 7, 19, 1, 8, 22, 4, 6, 15, 9, 2, 11, 17], want $k=8$ (the median).

Step 1 — groups of 5. [12,3,5,7,19] [1,8,22,4,6] [15,9,2,11,17] Why? Constant-size groups make per-group median trivial.

Step 2 — medians of each group (sort the 5, take middle):

• [3,5,7,12,19] → 7
• [1,4,6,8,22] → 6
• [2,9,11,15,17] → 11

Step 3 — median of medians of [7,6,11] → 7. So pivot $M=7$. Why this matters: 7 is guaranteed not to be near an extreme, so partitioning around it removes a constant fraction.

Step 4 — partition around 7: elements $<7$: [3,5,1,4,6,2] (6 of them) → 7 lands at index 7 (1-indexed). Since $k=8>7$, recurse right into [12,19,8,22,15,9,11,17] for the $(8-7)=1$st smallest = 8. ✅ (8 is indeed the median of the original.)

Worked example 2 — why a bad pivot would hurt (steel-man)

Same array, but suppose we pick pivot = 1 (the min).

Partition: nothing on the left, 1 lands at index 1. We must recurse into the remaining 14 elements. We removed only one element for $O(n)$ work.

Why this step shows the danger: if every pivot were a min/max, we'd do $O(n)+O(n-1)+\dots=O(n^2)$. MoM forbids this because $M$ always has $\ge \frac{3n}{10}$ elements on each side.

Common mistakes (Steel-man them)

Forecast-then-Verify

Pseudocode (self-contained)

Select(A, k):
    if len(A) <= 5:
        return sorted(A)[k-1]
    medians = [median(group) for group in chunks(A, 5)]
    M = Select(medians, ceil(len(medians)/2))      # median of medians
    L = [x for x in A if x < M]
    E = [x for x in A if x == M]
    G = [x for x in A if x > M]
    if k <= len(L):           return Select(L, k)
    elif k <= len(L)+len(E):  return M
    else:                     return Select(G, k - len(L) - len(E))

Why the 3-way split (L, E, G)? It safely handles duplicates of $M$ so we never recurse on a side that can't shrink.

Flashcards

Connections

• Quickselect — MoM is the pivot-choosing upgrade that makes it worst-case linear.
• Quicksort — same partition machinery; MoM pivot gives worst-case $O(n\log n)$ quicksort.
• Order statistics — median, min, max are special cases of selection.
• Master Theorem / Recurrence relations — but note MoM needs substitution, not the Master Theorem (unequal subproblems).
• Randomized algorithms — contrast: expected vs worst-case guarantees.
• Partitioning (Lomuto vs Hoare) — the engine behind step 4.

Concept Map

Hinglish (regional understanding)