merge_sort.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
def merge ary1, ary2
  new_ary = []
  until (ary1.empty? || ary2.empty?)
    if ary1.first < ary2.first
      new_ary << ary1.shift
    else
      new_ary << ary2.shift
    end
  end
  new_ary += ary1 + ary2
end

def sort ary
  return ary if ary.size == 1
  point = ary.size / 2
  ary_a = sort ary[0...point]
  ary_b = sort ary[point..-1]
  merge ary_a, ary_b
end

a = [8,4,3,7,6,5,2,1]
sort a # => [1, 2, 3, 4, 5, 6, 7, 8]