> Floyd and Rivest created the randomized
SELECT algorithm [12] in 1975. Although further improved and benchmarked with favorable results by Kiwiel [19], at the time of this writing we found no implementation available online and no evidence of industry adoption.
A search for "floyd rivest select" found a few different implementations, like
- https://softwareengineering.stackexchange.com/questions/2847...
- https://github.com/mourner/quickselect/blob/master/index.js
- http://dhost.info/zabrodskyvlada/3alg.html
A while ago, I also found that http://people.csail.mit.edu/rivest/pubs/FR75b.pdf is a more easily implementable description of SELECT, and also that it was significantly faster (3-4x) than quickselect (with naive pivot selection) when benchmarking the two on random data.