後記。以下の実装のほとんどはふつういうマージソートの実装ではありません。何かしら別物です。追記された merge_sort2.rb のみがふつういうマージソートの実装なので注意してください。というか、参考にしないで下さい。
- 作者: トーマス・H・コルメン,長尾高弘
- 出版社/メーカー: 日経BP社
- 発売日: 2016/03/11
- メディア: 単行本
- この商品を含むブログ (5件) を見る
merge_sort.rb
class Array def merge_sort return [] if empty? each_slice(1).to_a.merge end def merge #ar0, ar ar0 = [] each_slice(2) do |x| ar = [] if x.size == 1 ar = x[0] else while x[0].size.nonzero? and x[1].size.nonzero? ar.push((x[0][0] < x[1][0]) ? x[0].shift : x[1].shift) end ar += x[0] + x[1] end ar0 << ar end return ar0[0] if ar0.size == 1 ar0.merge end protected :merge end a = (0..10).to_a.shuffle a.merge_sort
Array#merge は分割されたソート済みの配列を2つずつ選んで結合します。結合をしているのは while 以下の 4行で、配列 x[0] と x[1] から値の小さい順に要素を選んで配列 ar に push します（値の小さい順に選んでいるので、配列 ar もソート済になります）。そしてそれを再帰的に繰り返し、すべて結合したら終了となります。
ここでの実装（これは本を参考にした）の方がすっきりしていますかねえ。でも、自力の実装もアルゴリズムに素直だという利点があると思います。
※追記（2018/2/9）
別様に実装してみました。
merge_sort1.rb
class Array def merge_sort join = lambda do |a, b| result = [] while a.size.nonzero? and b.size.nonzero? result.push((a[0] < b[0]) ? a.shift : b.shift) end result + a + b end msort = lambda do |ar| return ar[0] if ar.size <= 1 merged = [] ar.each_slice(2) {|a, b| merged << join.call(a, (b or []))} msort.call(merged) end msort.call(map {|x| [x]}) end end
アルゴリズムどおりに素直に実装しました。まず与えられた配列をバラバラにしてそれぞれを配列化します。関数 msort は二つずつ配列を取り出して join します。関数 join[a, b] は、ソート済の二つの配列 a, b を、うまくソート済になるように結合します。
※再追記（2018/3/12）
さらに別様に実装してみました。これがふつういうマージソートの実装です。
merge_sort2.rb
class Array def merge_sort merge = ->(a, b) { result = [] while a.size.nonzero? and b.size.nonzero? result.push((a[0] <= b[0]) ? a.shift : b.shift) end result + a + b } return self if length <= 1 q = length / 2 merge.(self[0...q].merge_sort, self[q..-1].merge_sort) end end
