2013
02.05

Deterministic median selection

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):

  1. Makefile.
  2. median_selection.C.
  3. timer.h.