Deterministic median selection
by Sariel on Feb.05, 2013, under Slowy
So, for fun, I had implemented the deterministic median selection in C++. It is about 4-5 times slower than QuickSelect, which is really not bad. Modern computers are amazingly fast – I run my algorithm on an input of size of 400 million random integers, and the computer sorted them, selected, etc, in a matter of a few minutes. Pretty impressive.
Anyway, I do think this indicates that deterministic median selection is practical – its just a bit slow – but is definitely a practical algorithm. Source code (linux):
This looks more like a C implementation than a C++ one. Anyway I think you are right about the algorithm being practical. I remember a (very good) student working on a hard question we gave at TAU when I was a teaching assistant saying “there has to be a linear algorithm for finding the median to solve this one” and when I told him that there is one and explained it to him he thought that it is totally impractical. His background was engineering but he was a very intelligent student. Since then I’ve shown it to many students and it’s usually a hard one to explain although coding it can be done in very few lines of code. I think you should try to use a sorting algorithm not only for arrays less than 10, but also for arrays less than 80 or so (maybe quicksort instead of insertion sort). I think it could improve the runtime a bit.