Rubyでアルゴリズムやらデータ構造やらのお勉強（Merge Sort）

merge_sort.rb

# -*- coding: utf-8 -*-

# Cで書かれたアルゴリズムやらデータ構造なりを、自分なりにRubyで表現してみるお勉強PJ。
# 参考書籍（プログラミングの宝箱 アルゴリズムとデータ構造）
# Ruby1.9.3で動作確認済み

# と言っといてなんだけど、同書籍にCじゃなくJava版もあったので今度はそちらをもとにした。
# ところがこれもというかなおさらというか読みやすくはない。
# どちらにせよ１文字のカウンタ変数とか使われると、この広さはすでに読むのしんどいなー。
# (古本で入手したんだけど、そもそもC版の方の変数名に前所有者の解説コメントが。ということはやっぱ直感的じゃないのでは)
# これも要見直し

$VERBOSE = true

class Array

  def merge_sort!
    _merge_sort! self, self.size, 0
    self
  end

  private

  def _merge_sort!(list, block_size, offset)
    return if block_size <= 1

    head_size = block_size / 2

    _merge_sort! list, head_size, offset
    _merge_sort! list, block_size - head_size, offset + head_size

    buffer = []

    (0...head_size).each do |n|
      buffer[n] = list[offset + n]
    end

    j, i, pos = head_size, 0, 0

    while i < head_size && j < block_size
      if buffer[i] <= list[offset + j]
        list[offset + pos] =  buffer[i]
        i += 1
      else
        list[offset + pos] = list[offset + j]
        j += 1
      end

      pos += 1
    end

    (i...head_size).each do |n|
      list[offset + pos] = buffer[n]
      pos += 1
    end
  end

end


# Overview

list = (-50..50).to_a.shuffle
p list
p list.object_id
p list.merge_sort!
p list.object_id