Rubyでアルゴリズムやらデータ構造やらのお勉強（Merge Sort / マージソート）- 2

mergesort.rb

# coding: us-ascii
# 2015 Kenichi Kamiya

class Array
  # [6, 5, 1, 4, 3] => [1, 3, 4, 5, 6]
  def mergesort
    case size
    when 0, 1
      self
    when 2
      if first > last
        [last, first]
      else
        self
      end
    else
      split_half.map(&:mergesort).merge_sorted_pair!
    end
  end

  # [6, 5, 1, 4]    => [[6, 5], [1, 4]]
  # [6, 5, 1, 4, 3] => [[6, 5, 1], [4, 3]]
  def split_half
    short, excess = *size.divmod(2)
    each_slice(short + excess).to_a
  end
  
  # [[1, 5, 6], [3, 4]] => [1, 3, 4, 5, 6]
  # destructive for pair
  def merge_sorted_pair!
    merged = []
    
    until first.empty? && last.empty?
      merged << case
                when first.empty?
                  last.shift
                when last.empty?
                  first.shift
                when first.first > last.first
                  last.shift
                when last.first > first.first
                  first.shift
                else
                  raise 'should not reach here'
                end
    end

    merged
  end
  
  # [[1, 5, 6], [3, 4]] => [1, 3, 4, 5, 6]
  # non-destructive for pair
  # def merge_sorted_pair
  #   merged = []
  #   
  #   fi, li = 0, 0
  #   while (fi < first.size || li < last.size)
  #     if fi < first.size
  #       if li >= last.size || first[fi] <= last[li]
  #         merged << first[fi]
  #         fi += 1
  #       end
  #     end
  #     
  #     if li < last.size
  #       if fi >= first.size || last[li] <= first[fi]
  #         merged << last[li]
  #         li += 1
  #       end
  #     end
  #   end
  # 
  #   merged
  # end
end

# Overview

list = [6, 5, 1, 4, 3]
p list
p list.mergesort

list = (-10..10).to_a.shuffle
p list
p list.mergesort

昔書いたのがあまりにも読みづらかったので、もうちょっと思い出しやすい形にまとめ直してみた