#median-of-medians

Median of Medians

Median of Medians Median of Medians is a pivot selection method for deterministic linear-time selection. It chooses a pivot that is good enough to discard a constant fraction of the input after partitioning. The method is most often used inside Deterministic Select. It gives worst-case guarantees, but it has larger constant factors than randomized pivot selection. Problem Given an array $A$, choose a pivot value that is close enough to...