The Median-of-Medians Selection Algorithm

Manuel Eberl 🌐

December 21, 2017

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

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