Sample code from a blog post I wrote

merge_sort.rb

def merge_sort(a)
  return a if a.length <= 1
 
  first_half = a.first(a.length / 2)
  second_half = a.last(a.length - a.length / 2)
  sorted_first_half = merge_sort(first_half)
  sorted_second_half = merge_sort(second_half)
 
  merge_step(sorted_first_half, sorted_second_half)
end
 
def merge_step(l, r)
  merged = []
  while l.any? and r.any?
    if l.first < r.first
      merged << l.shift
    else
      merged << r.shift
    end
  end
  merged + l + r
end