【アルゴリズムの勉強】Rubyでマージソートを書いてみる

アルゴリズムの勉強としてRubyマージソートを実装する。

マージソートとは

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]。
(ナイーブな)クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。

マージソート - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count
buffer = []

def merge_sort(arr, left, right, buffer)
  if left < right
    center = (left + right) / 2
    first_r = 0
    first_l = 0
    right_cursor = left
    left_cursor = left

    merge_sort(arr, left, center, buffer)
    merge_sort(arr, center + 1, right, buffer)

    while right_cursor <= center
      buffer[first_r] = arr[right_cursor]
      first_r += 1
      right_cursor += 1
    end

    while right_cursor <= right && first_l < first_r
      if buffer[first_l] <= arr[right_cursor]
        arr[left_cursor] = buffer[first_l]
        left_cursor += 1
        first_l += 1
      else
        arr[left_cursor] = arr[right_cursor]
        left_cursor += 1
        right_cursor += 1
      end
    end

    while first_l < first_r
      arr[left_cursor] = buffer[first_l]
      left_cursor += 1
      first_l += 1
    end
  end
  return arr
end

sorted_arr = merge_sort(arr, 0, number_of_elements - 1, buffer)
p sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]

参考文献、参考リンク