Median of Medians

Core Idea

Normal Quick Sort can degrade to O(n^2) if the pivot choices are consistently bad.

If we always choose the true median as the pivot, the array is split almost exactly in half:

T(n) = 2T(n/2) + O(n)
     = O(n log n)

Role of Median of Medians

Median of Medians is a deterministic pivot-selection method used with Quick Select.

• Split elements into groups, usually of 5
• Find the median of each group
• Find the median of those medians
• Use it as a good pivot

This guarantees Quick Select runs in O(n) worst-case time.

So we can find the actual median of an array in O(n).

Connecting It to Quick Sort

At each Quick Sort step:

1. Find the median using Median of Medians + Quick Select → O(n)
2. Use the median as the pivot and partition → O(n)
3. The two sides have roughly n/2 elements each
4. Recurse on both sides

Therefore:

T(n) = 2T(n/2) + O(n)
     = O(n log n)

One-Line Summary

If we find the median in O(n) using Median of Medians + Quick Select and use it as Quick Sort’s pivot, Quick Sort becomes O(n log n) even in the worst case.

Note

• Normal Quick Sort
  • Average: O(n log n)
  • Worst: O(n^2)
• Quick Sort with Median of Medians
  • Worst: O(n log n)
• In practice, this is often slower because of larger constant factors, so randomized pivots are more common.

References

• https://www.acmicpc.net/problem/16455