Ruby マージソート実装

今回はArrayクラスに組み込んだ。
Rubyでは配列外アクセスはnilが帰るだけなので、番兵じゃなくても良い気がするが、ここはセオリーに従い実装。

class Array
  def merge_sort!(s = 0, e = size-1, inf = max+1)
    return if e <= s

    center = (s + e) / 2

    merge_sort!(s, center, inf)
    merge_sort!(center + 1, e, inf)

    left  = self[s..center]       << inf
    right = self[(center + 1)..e] << inf

    r = l = 0
    s.upto(e) do |i|
      if left[l] > right[r]
        self[i] = right[r]
        r += 1
      else
        self[i] = left[l]
        l += 1
      end
    end
  end
end

a = [3, 2, 1, 5, 3]
a.merge_sort!
p a
# => [1, 2, 3, 3, 5]

分割、マージの様子はこうなってるはず。

[3, 2, 1, 5, 3]
[3, 2, 1][5, 3]
[3, 2][1][5][3]
[3][2][1][5][3]
[2, 3][1][5][3]
[1, 2, 3][3, 5]
[1, 2, 3, 3, 5]

マージ時のキモは14行目のupto部分で、たとえば以下のleftとrightをマージする場合

left  = [2,5,10,INF]
right = [6,8,9,INF]

left, rightのそれぞれはソート済みであるので、先頭から小さい方の値を取り出していくと、２つの配列を合わせたソート済みの配列を作れる。
※ INFは番兵（十分に大きい数）

[2,5,10,INF] < [6,8,9,INF] なので 2
[2,5,10,INF] < [6,8,9,INF] なので 5
[2,5,10,INF] > [6,8,9,INF] なので 6
[2,5,10,INF] > [6,8,9,INF] なので 8
[2,5,10,INF] > [6,8,9,INF] なので 9
[2,5,10,INF] < [6,8,9,INF] なので 10

よって以下の配列が得られる

[2, 5, 6, 8, 9, 10]

この流れは結構好み。