【Ruby】sort を使わずにマージソートをする

Rubyでマージソートのアルゴリズムを作る

あえてRubyのsortを使用せずにRubyでマージソートのアルゴリズムを書いてみる。

マージソート

def merge_sort(array)
  return array if array.length <= 1
  mid = array.length / 2
  first_array = array.slice(0..mid - 1)
  second_array = array.slice(mid..-1)

  first_array = merge_sort(first_array)
  second_array = merge_sort(second_array)

  result = []
  until first_array.empty? and second_array.empty?
    if first_array.empty?
      result.concat(second_array)
      second_array.clear
    elsif second_array.empty?
      result.concat(first_array)
      first_array.clear
    else
      if first_array.first < second_array.first
        result << first_array.shift
      else
        result << second_array.shift
      end
    end
  end
  result
end

puts "スペースで区切って数値を入力してください"
list = gets
print merge_sort list.split(" ").map(&:to_i)

参考文献

Rubyのsort組み込みライブラリ
https://docs.ruby-lang.org/ja/latest/method/Array/i/sort.html

Wikipedia マージソート
https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88#:~:text=%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88%E3%81%AF%E3%80%81%E3%82%BD%E3%83%BC%E3%83%88%E3%81%AE,%E4%BD%9C%E6%A5%AD%E3%81%AF%E4%B8%A6%E5%88%97%E5%8C%96%E3%81%A7%E3%81%8D%E3%82%8B%E3%80%82