def merge(l, r)
  return l if r.empty?
  return r if l.empty?
  x, *xs = l
  y, *ys = r
  return [x, *merge(xs, r)] if x <= y 
  [y, *merge(l, ys)]
end 

def msort(li)
  return li if li.length < 2
  xs, ys = halve(li)  
  merge(msort(xs), msort(ys))  
end

def halve(li)
  xs = li.take(li.length / 2)
  ys = li.drop(li.length / 2)
  [xs, ys]
end

p merge([2,4,6],[1,3,5])
p msort([3,2,4,1,5])