マージソート

Slashdot.jp で、初めて学ぶソートアルゴリズムは何がいい? という話題があった。

ちょくちょくマージソートが紹介されていたので作ってみた。

まずはマージ。

module Enumerable
  def merge(o)
    i = 0
    j = 0
    m = []
    while i < size && j < o.size
      if self[i] < o[j]
        m << self[i]
        i += 1
      else
        m << o[j]
        j += 1
      end
    end

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

[1, 2, 3].merge [4, 5]          # => [1, 2, 3, 4, 5]
[4, 5].merge [1, 2, 3]          # => [1, 2, 3, 4, 5]
[1, 2, 3].merge [1, 2, 3]       # => [1, 1, 2, 2, 3, 3]
[1, 3, 5].merge [2, 4, 6]       # => [1, 2, 3, 4, 5, 6]
[1].merge [1]                   # => [1, 1]
[].merge []                     # => []

Enumerable::Enumerator で書けないか頑張ってみたけど、添字を使った方が簡単だった。

そしてソート。

module Enumerable
  def msort
    return self  if size <= 1
    n = size / 2
    self[0...n].msort.merge self[n..-1].msort
  end
end

a = (1..10).to_a.shuffle        # => [5, 3, 6, 8, 1, 4, 7, 2, 10, 9]
a.msort                         # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

動いた。

でも、Ruby の sort には、

• sort
• sort {|a, b| ... }
• sort_by {|item| ... }

の 3 種類がある。

sort_by は sort {|a, b| ... } を使って作るのかな?

msort {|a, b| ... } を作るには merge {|a, b| ... } が必要。

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
end

[3, 2, 1].merge([5, 4]) {|a,b| b<=>a} # => [5, 4, 3, 2, 1]
[5, 4].merge([3, 2, 1]) {|a,b| b<=>a} # => [5, 4, 3, 2, 1]
["1", "5", "10"].merge(["2", "4", "8", "16"]){|a,b| a.to_i <=> b.to_i}
# => ["1", "2", "4", "5", "8", "10", "16"]

さて、これを msort {|a, b| ... } から使うには ... どうしたらいいんだ?

msort はブロックを使うわけじゃなくて、merge に渡したいだけなんだけど ...