Course contentsShow
← Computer Science
Lesson 826 of 2,87219. Searching and SelectionFree lesson

Median of Medians: Partitioning Strategy

Understanding how dividing into groups of 5, finding medians, and recursively selecting ensures good pivot quality.

Median of Medians: Partitioning Strategy

What you'll learn: How the Median of Medians algorithm guarantees a good pivot by dividing data into groups of 5, finding their medians, and recursively selecting the "median of medians."

The Core Problem

In the previous lesson, you saw that Median of Medians provides deterministic worst-case linear time selection. But how does it actually guarantee a good pivot? The answer lies in its clever partitioning strategy.

The 5-Step Strategy

The algorithm ensures quality pivots through this process:

  1. Divide into groups of 5: Split your array into ⌈n/5⌉ groups of 5 elements each (last group may be smaller)
  2. Find each group's median: Sort each small group and pick its middle element — this takes constant time per group since groups have fixed size
  3. Recursively find the median of medians: Gather all those medians into a new array and recursively select their median
  4. Use as pivot: This "median of medians" becomes your partition pivot
  5. Partition and recurse: Partition around this pivot and recurse on the appropriate side

Why Groups of 5?

The magic number 5 ensures mathematical balance. When you partition around the median of medians:

  • At least half of the group medians are ≤ the pivot
  • Each of those groups contributes at least 3 elements ≤ the pivot
  • This guarantees roughly 30% of elements are eliminated per step

This is enough to ensure O(n) worst-case time, unlike randomized QuickSelect which can degrade to O(n²).

Think of it like: Instead of blindly picking a pivot (which might be terrible), you're pre-screening candidates by organizing them into small committees, finding each committee's representative, then choosing the most "middle" representative.

Key Takeaway: The Median of Medians partitioning strategy guarantees pivot quality by recursively selecting from carefully chosen group representatives, ensuring balanced partitions and O(n) worst-case performance.