マージソート(Ruby)

アルゴリズムの基本

アルゴリズムの基本

マージソートアルゴリズムだけ勉強して、自力で 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 もソート済になります)。そしてそれを再帰的に繰り返し、すべて結合したら終了となります。
 
 
ここでの実装(これは本を参考にした)の方がすっきりしていますかねえ。でも、自力の実装もアルゴリズムに素直だという利点があると思います。