Mergesort in Ruby

Posted by Moser on 18 Sep 2008

While playing around with stable sorting I implemented Mergesort.

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

It is not suitable for productive use as it’s quite slow. It’s about ten times slower than the stable_sort method from my another post. A little benchmark sorting an array of 2,000,000 random integers:

                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)
blog comments powered by Disqus