マージソート

ソート済みの２つの配列をマージ（結合）することでソートを行う。
配列を２つに分割するため、分割統治法を用いているソートとなる。
計算量はO(nlogn)であり、傾向はヒープソートと同じである。
しかし、配列の左部分をバッファに退避するため、要素数に比例したメモリを使用することになる。

今回は２つの場合に大別して実装を行った。

1. 2分割した配列それぞれに要素が存在するとき
2. 2分割した配列の一方にのみ要素が存在するとき

なお、参考書では、次のような実装となっている。

1. 2分割した配列の一方がすべてマージ済みとなるまで、比較と基準値の更新を処理を繰り返す
2. 上の処理が終了したら、残った一方をすべて配列に挿入する

参考書実装の方がコードは読みやすいが、ストレートな処理ではないので少し理解が難しくなると思う。

def mergesort!(array, left, right)
  if(left < right) then
    #部分配列の要素数が２つ以上なら処理を行う
    
    #分割した左右についてマージソート
    center = (left + right) / 2
    mergesort!(array, left, center)
    mergesort!(array, center + 1, right)

    #作業のためバッファに左部分配列をコピー
    buffer = Array.new(center - left + 1)
    0.step(buffer.size, 1) do |i|
      buffer[i] = array[left + i]
    end

    #マージのための初期化処理
    target = left	#配列へ要素を挿入する位置
    pl = 0		#バッファの参照位置
    pr = center + 1	#右部分の参照位置
    center = center - left

    while (pl <= center || pr <= right) do
      #２つの配列のいずれかに要素が存在する間マージを繰り返す  
      if(pl <= center && pr <= right)then
        #２つの配列のどちらも要素が存在するとき
        if(buffer[pl] < array[pr])then
          #左部分の比較要素の方が小さいとき
          array[target] = buffer[pl]
          pl += 1
        else
	  #右部分の比較要素の方が小さいとき
          array[target] = array[pr]
          pr += 1
        end
      else
        #２つの配列の一方にだけ要素が存在するとき
        if(pl <= center)then
          array[target] = buffer[pl]
          pl += 1
        elsif(pr <= right)then
          array[target] = array[pr]
          pr += 1
        end
      end
      #挿入位置を１つずらす
      target += 1
    end
    p array
  end
end

def startMergeSort(array)
  mergesort!(array, 0, array.size - 1)
end

data = Array.new
while input = $stdin.gets.to_i
  break if input < 0
  data << input
end

p data
startMergeSort(data)
p data

机上での動作確認に１時間、実装・デバッグに１時間かかった。
コードを参考にしていた時間とJavaScriptで遊んでいた時間を含めると合計で５時間。
頭で考えても理解できないのだから、早めに机上で動作確認するが吉。
前にも同じことを書いた気がする。