マージソートにブロックを渡す

この前作ったマージソートをブロック付きメソッドに変更できた。

module Enumerable
  def merge(o, &comp)
    comp = Proc.new{|a,b| a<=>b}  if comp.nil?
    i = 0
    j = 0
    m = []
    while i < size && j < o.size
      if comp [self[i], o[j]] <= 0
        m << self[i]
        i += 1
      else
        m << o[j]
        j += 1
      end
    end

    m += self[i..-1]
    m += o[j..-1]
  end

  def msort(&comp)
    return self  if size <= 1

    comp = Proc.new{|a,b| a<=>b}  if comp.nil?
    n = size / 2
    self[0...n].msort{|a,b| comp [a, b]}.
      merge(self[n..-1].msort{|a,b| comp [a, b]}){|a,b| comp [a, b]}
  end
end

a = (1..15).to_a.map{|i| "#{i}"}.shuffle
# => ["14", "8", "9", "4", "10", "6", "12", "5", "3", "1", "7", "11", "2", "15", "13"]
a.msort
# => ["1", "10", "11", "12", "13", "14", "15", "2", "3", "4", "5", "6", "7", "8", "9"]
a.msort{|a, b| a.to_i <=> b.to_i}
# => ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15"]

受けとったブロックを新たなブロックの中で呼ぶだけでよかったのか。

Wikipedia を見てみたら、マージソートは安定ソートでないといけないらしいので、こっそり修正。

["1a", "1b", "2a", "2b"].msort{|a,b| a.to_i<=>b.to_i}  # => ["1a", "1b", "2a", "2b"]
["1a", "1b", "2a", "2b"].msort{|a,b| b.to_i<=>a.to_i}  # => ["2a", "2b", "1a", "1b"]

元の配列で前にあった方が、ソート後の配列でもちゃんと前にある。