If you're selecting the n:th element, where n is very small (or large), using median-of-medians may not be the best choice.
Instead, you can use a biased pivot as in [1] or something I call "j:th of k:th". Floyd-Rivest can also speed things up. I have a hobby project that gets 1.2-2.0x throughput when compared to a well implemented quickselect, see: https://github.com/koskinev/turboselect
If anyone has pointers to fast generic & in-place selection algorithms, I'm interested.
Instead, you can use a biased pivot as in [1] or something I call "j:th of k:th". Floyd-Rivest can also speed things up. I have a hobby project that gets 1.2-2.0x throughput when compared to a well implemented quickselect, see: https://github.com/koskinev/turboselect
If anyone has pointers to fast generic & in-place selection algorithms, I'm interested.
[1] https://doi.org/10.4230/LIPIcs.SEA.2017.24