Deterministic median-finding

[Tom Hayes]

Hi class,

Here is a relevant article on wikipedia.

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22

The key point I was missing: Once you find the median of medians, use
that as
a PIVOT to split the list into two parts. We can argue that, by the
median of medians
property, at least a constant fraction of the list will be on each
side of the pivot, and
hence the subproblem remaining is substantially smaller.

Tom