# The Median-of-Medians Selection Algorithm

 Title: The Median-of-Medians Selection Algorithm Author: Manuel Eberl Submission date: 2017-12-21 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. BibTeX: @article{Median_Of_Medians_Selection-AFP, author = {Manuel Eberl}, title = {The Median-of-Medians Selection Algorithm}, journal = {Archive of Formal Proofs}, month = dec, year = 2017, note = {\url{http://isa-afp.org/entries/Median_Of_Medians_Selection.html}, Formal proof development}, ISSN = {2150-914x}, } License: BSD License Used by: KD_Tree