Awesomely fast order statistic estimator (guaranteed linear time).
Reference
Andrei Alexandrescu, Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, Rajeev Raman “Fast Deterministic Selection” (2017) // 16th International Symposium on Experimental Algorithms (SEA 2017). Publisher: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. Dagstuhl, Germany. ISBN: 978-3-95977-036-1. Vol. 75. Pp. 24:1–24:19. DOI: 10.4230/LIPIcs.SEA.2017.24
Bib
@Inproceedings{alexandrescu2017,
author = {Andrei Alexandrescu},
title = {Fast Deterministic Selection},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {24:1--24:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
isbn = {978-3-95977-036-1},
issn = {1868-8969},
year = {2017},
volume = {75},
editor = {Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
url = {http://drops.dagstuhl.de/opus/volltexte/2017/7612},
urn = {urn:nbn:de:0030-drops-76122},
doi = {10.4230/LIPIcs.SEA.2017.24},
arxiv = {1606.00484},
annote = {Keywords: Selection Problem, Quickselect, Median of Medians, Algorithm Engineering, Algorithmic Libraries}
}