Improved randomized selection
<|reference_start|>Improved randomized selection: We show that several versions of Floyd and Rivest's improved algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+O(n^{1/2}\ln^{1/2}n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Encouraging computational results on large median-finding problems are reported.<|reference_end|>
@article{kiwiel2004improved,
    title={Improved randomized selection},
    author={Krzysztof C. Kiwiel},
    journal={arXiv preprint arXiv:cs/0402005},
    year={2004},
    number={PMMO-04-02},
    archivePrefix={arXiv},
    eprint={cs/0402005},
    primaryClass={cs.DS}
}