The Median-of-Medians Selection Algorithm

Manuel Eberl

21 December 2017


This entry provides an executable functional implementation of the Median-of-Medians algorithm for selecting the k-th smallest element of an unsorted list deterministically in linear time. The size bounds for the recursive call that lead to the linear upper bound on the run-time of the algorithm are also proven.

BSD License

Used by