Note that you shouldn't use the algorithm in practice (unless you need certain guarantees) since the average performance isn't that great. This is just like Mer

Note that you shouldn't use the algorithm in practice (unless you need certain guarantees) since the average performance isn't that great. This is just like Mergesort vs Quicksort where Mergesort guarantees O(NlogN) yet Quicksort is usually much faster. The constant for the number of comparisons is quite high. Compare this to the average complexity for Quickselect with these pivot strategies: - Random pivot (ie Median of 1) has 3.39N comparisons - Median of 3 has 2.75N If you want the fastest possible algorithm you should follow http://dx.doi.org/10.1109/TSP.2012.2197394 http://dx.doi.org/10.1109/TSP.2012.2197394 which proposes to choose the median of N^{2/3}1/(4pi)^{1/3} elements as the pivot and then also uses a different strategy to choose the second pivot (close to the median yet "safe"). Another fast algorithm is Floyd & Rivest's SELECT (yes the same crypto Rivest) which is also asymptotically optimal and implementations exist. (Paper title: "Expected time bounds for selection")