マージソート - Camera Obscura

プログラムの性質上、破壊的なメソッドになります。

merge_sort.rb

class Array
  def merge(p, q ,r)
    left = self[p..q] + [Float::INFINITY]
    right = self[(q + 1)..r] + [Float::INFINITY]
    i = j = 0
    for k in p..r
      if left[i] <= right[j]
	self[k] = left[i]
	i += 1
      else
	self[k] = right[j]
	j += 1
      end
    end
  end
  
  def merge_sort(p, r)
    return if p >= r
    q = (p + r) / 2
    merge_sort(p, q)
    merge_sort(q + 1, r)
    merge(p, q, r)
    self
  end
end

p [6, 0, 5, 2, 3].merge_sort(0, 4)    #=>[0, 2, 3, 5, 6]