sort.rb

class Array
  def merge_sort(&block)
    return self if size < 2

    block ||= lambda { |a, b| a <=> b }

    half_size = size / 2

    first_ary  = self[0, half_size].merge_sort(&block)
    second_ary = self[half_size, size].merge_sort(&block)

    ary = []
    first_ary.each do |elem|
      while second_ary.first && block[second_ary.first, elem] < 0
        ary << second_ary.shift
      end

      ary << elem
    end

    ary.concat(second_ary)
  end
end