プログラムの性質上、破壊的なメソッドになります。
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]
アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)
- 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
- 出版社/メーカー: 近代科学社
- 発売日: 2012/08/02
- メディア: 単行本
- 購入: 1人 クリック: 16回
- この商品を含むブログ (19件) を見る
※追記(2017/7/20)
自力で Ruby で実装してみました。