The Big Programming Thread - Page 895

Generate all possible decision trees recursively, so that at each step:

1. see if we can already definitely select the median element based on the current list of performed comparisons
   (count number of known greater and known smaller elements for each element 
     - if some element has N/2 for both then we know the median)

2. if not, pick a pair of elements whose order isn't known yet

3. add that pair to the decision tree, try both possible comparison results for that pair 
   and generate recursively the remaining decision tree for each result if possible

4. fail fast if the decision tree is too deep 
    (and would require more comparisons than the known optimal amount)

5. fail if either of the child nodes can't be solved within the remaining number of comparisons

sort a,b <- a is now smallest of these 2, 1 comparison
sort c,d <- c is now smallest of these 2, 2 comparisons
if a < c: <- 3 comparisons
  sort b, e <- b is now smallest of these 2, 4 comparisons
  if b < c: <- 5 comparisons
     if e < c: <- 6 comparisons
        return e
     else return c
  else:
     if d < b: <- 6 comparisons
       return d
     else return b
else:
  Same as above, but with (a,b), (d,e)