The Median-of-Medians Selection Algorithm

Manuel Eberl 🌐

December 21, 2017

Abstract

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

Topics

Theories of Median_Of_Medians_Selection