class Array
  def mergesort(&cmp)
    if cmp == nil
      cmp = lambda { |a, b| a <=> b }
    end
    if size <= 1
      self.dup
    else
       halves = split.map{ |half|
        half.mergesort(&cmp)
      }
      merge(*halves, &cmp)
    end
  end
 
 
  protected
  def split
    n = (length / 2).floor - 1
    [self[0..n], self[n+1..-1]]
  end
 
  def merge(first, second, &predicate)
    result = []
    until first.empty? || second.empty?
     if predicate.call(first.first, second.first) <= 0
        result << first.shift
      else
        result << second.shift
      end 
    end
    result.concat(first).concat(second)
  end
end

                user     system      total        real
Original Sort 0.630000   0.010000   0.640000 (  0.639860)
Stable Sort 12.780000   0.700000  13.480000 ( 13.477982)
Mergesort 109.170000  13.420000 122.590000 (122.617323)