[betterunix2]

The textbook solution is to use this pivot selection algorithm:

https://en.wikipedia.org/wiki/Median_of_medians

In practice it is not really worth it.

[jchanimal]

No matter how clever you are with an algorithm, somebody wrote a paper on it in the 70s.