『基礎から学ぶデータ構造とアルゴリズム』「4.5 マージソート」の勉強メモです。自分なりに咀嚼したソート手順とサンプルコード（Ruby）をまとめています。

数字列を真ん中で二つの部分列に分割する
二つの部分列をそれぞれ整列する。これを再帰的に行う
整列済みの部分列をマージする

def merge_sort(a, n)
  return if n <= 1

  # a の前半をソート
  m = n / 2
  merge_sort a, m

  # a の後半を b にコピーしてソート
  b = a[m..(n - 1)]
  merge_sort b, n - m

  # a の前半を a の後半にコピー
  a[(n - m)..(n - 1)] = a[0..(m - 1)]

  # a の後半と b を大小比較しつつマージ
  ri = 0
  ai = n - m
  bi = 0
  while bi < n - m
    if ai < n && a[ai] <= b[bi]
      a[ri] = a[ai]
      ai += 1
    else
      a[ri] = b[bi]
      bi += 1
    end
    ri += 1
  end
end

a =  [10, 25, 75, 5, 30, 35, 15, 90, 65, 80, 50, 45]
merge_sort(a, a.size)
p a

[5, 10, 15, 25, 30, 35, 45, 50, 65, 75, 80, 90]

マージソート

リンク