Implementation of the linear time median of medians algorithm.

median.rb

# Gist to go with http://www.austinrochford.com/posts/2013-10-28-median-of-medians.html
# Chad Brewbaker   10/28/2013
#  https://news.ycombinator.com/item?id=6628474

def median_5(list, i = list.length/2)
  return list.sort[i]
end

def median(list, i = list.length/2)
  if (list.length <= 5)
    return median_5(list, i)
  end
  median_list = []
  list.each_slice(5) { |s|
    median_list.push(median_5(s))
  }
  more =[]
  less = []
  pivot = median(median_list)
  less = list.find_all { |x| x < pivot }
  if (i < less.length)
    return median(less, i)
  end
  if (i == less.length)
    return pivot
  end
  more = list.find_all { |x| x > pivot }
  return median(more, i-(less.length+1))
end

test = (1..1000).select { |x| true }
puts test.length.to_s + " elements in the test array"
0.upto(5) do |iteration|
  test = test.shuffle!
  0.upto(test.length-1) do |i|
    if median(test, i) != test.dup.sort[i]
      puts median(test, i).to_s + " != " + test.dup.sort[i].to_s
    end
  end
end