What is the name of the 'divide and conquer' algorithm used to find the median of an unsorted array in O(n) worst-case time?
Show answer
Median-of-medians (or Select)
The Median-of-medians algorithm partitions the array into groups of five to find a 'good' pivot. This ensures a balanced split in the recursion, preventing the O(n^2) worst-case behavior typical of the standard Quickselect.
Also asked as:
- Which algorithm finds the median of an unsorted array in O(n) worst-case time by partitioning the array into groups of five?