Median of medians

Common card · No. 373504

In computer science, the median of medians is an approximate median selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, most commonly quickselect, that selects the kth smallest element of an initially unsorted array. Median of medians finds an approximate median in linear time. Using this approximate median as an improved pivot, the worst-case complexity of quickselect reduces from quadratic to linear, which is also the asymptotically optimal worst-case complexity of any selection algorithm. In other words, the median of medians is an approximate median-selection algorithm that helps building an asymptotically optimal, exact general selection algorithm (especially in the sense of worst-case complexity), by producing good pivot elements. Median of medians can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O ( n log ⁡ n...

Read on Wikipedia · Image Pashapanther, CC BY-SA 3.0