title: Fastest code C/C++ to select the median in a set of 27 floating point values
body: <p>This is the well know select algorithm. see <a href="http://en.wikipedia.org/wiki/Selection_algorithm" rel="noreferrer">http://en.wikipedia.org/wiki/Selection_algorithm</a>.</p>
  
  <p>I need it to find the median value of a set of 3x3x3 voxel values. Since the volume is made of a billion voxels and the algorithm is recursive, it better be a little bit fast. 
  In general it can be expected that values are relatively close.</p>
  
  <p>The fastest known algorithm I have tried out so far uses the quick sort partition function. I would like to know if there is a faster one. </p>
  
  <p>I've "invented" a 20% faster one using two heaps, but expected an even faster one using a hash. Before implementing this, I'd like to know if a blitz fast solution already exist out there. </p>
  
  <p>The fact that I'm using floats shouldn't matter since they can be considered as unsigned integer after inverting the sign bit. The order will be preserved.</p>
  
  <p>EDIT: benchmark and source code moved into a separate answer as suggested by 
  Davy Landman. See below for the answer by chmike.</p>
  
  <p><strong>EDIT</strong>: The most efficient algorithm so far was referenced below by  Boojum as a link to the <a href="http://www.shellandslate.com/fastmedian.html" rel="noreferrer">Fast Median and Bilateral Filtering</a> paper which is now the answer to this question. The first smart idea of this method is to use radix sort, the second is to combine median search of adjacent pixels who share a lot of pixels.</p>