マージソート覚書（アルゴリズム・イントロダクション）

分割統治法

1. ソートすべきn要素の配列をn/2の部分列に分割する。
2. 2つの部分列を再帰的にソートする。
3. ソートされた部分文字列をマージする。

実装（Ruby)

擬似コードと同じように実装しようとしたら配列の境界エラーでコケまくり。

Infinity = 2**30

def merge(a, p, q, r)
  # p,q,rは配列の添字
  # p ≦ q ＜ r
  # a[p..q]とa[q+1..r]はともにソート済みと仮定する
  return a[p] if p == r
  n1 = q - p + 1
  n2 = r - q
  _L = a[p..p + n1 - 1]
  _R = a[q+1..q+n2]
  _L += [Infinity]
  _R += [Infinity]
  i = 0
  j = 0
  p.upto(r) do |k|
    if _L[i] <= _R[j]
      a[k] = _L[i]
      i += 1
    else
      a[k] = _R[j]
      j += 1
    end
  end
end

def merge_sort(a,p,r)
  if p < r
    q = (p+r)/2
    merge_sort(a, p, q)
    merge_sort(a, q+1, r)
    merge(a, p, q, r)
  end
  a
end

正しい挙動をしているのかどうか怪しいのでテストを書いてみる。
テストは保守性の面でプログラマが安心を得るためのものなので、書き捨てのコードに書いても意味ないけど、テスト書いてみたかったので。
特殊なケースは考えずにランダムな配列に通ればいいとする。

require "test/unit"
require "./merge"

class TC_Merge < Test::Unit::TestCase
  def test_merge_sort
    1000.times do |i|
      a = Array.new(1000).map{|i| rand 10000}
      assert_equal(a.sort, merge_sort(a,0,a.length-1))
    end
  end
end

結果

Loaded suite test_merge
Started
.
Finished in 7.320000 seconds.

1 tests, 1000 assertions, 0 failures, 0 errors, 0 skips

Test run options: --seed 20452

ちゃんと動いてるみたい。

ベンチマーク

要素が多ければ挿入ソートより遥かに速いことが分かる（前記事参照）。と言っても要素数100,000で7秒はちょっとかかり過ぎかな…
ちなみにこれはArray#sortで1000万要素を整列した時と同じくらいの時間だった。2ケタも違うのか。

追記 2012.3.28

アルゴリズムイントロダクション上は図書館に返却したため絶賛放置中。全然読めなかった。