マージソート(Ruby)

後記。以下の実装のほとんどはふつういうマージソートの実装ではありません。何かしら別物です。追記された merge_sort2.rb のみがふつういうマージソートの実装なので注意してください。というか、参考にしないで下さい。
 



アルゴリズムの基本

アルゴリズムの基本

マージソートアルゴリズムだけ勉強して、自力で Ruby で実装してみました。

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].any? and x[1].any?
          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.any? and b.any?
        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.any? and b.any?
        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