msort.rb

def split xs
  if xs.size == 1 then return [xs, []] end
  [xs[0..(xs.length / 2 -1)],
   xs[(xs.length / 2)..-1  ]]
end

def merge args
  l, r = args
  inf = 1.0 / 0

  l << inf
  r << inf
  xs = (1..(l.size + r.size - 2)).map do
    (l.first <= r.first) ? l.shift : r.shift
  end

end

def msort xs
  l, r = split xs
  merge(if (xs.size <= 2)
          [l, r]
	else
          [(msort l), (msort r)]
	end)
end


xs = (1..20).sort{|x,y| rand}

p xs
p msort(xs)