Rubyでマージソート

ちょっと気が向いたので、マージソートを見ながらRubyでマージソートを実装してみました(自分で書いたソートのルーチンを実際使うかどうかは置いておいて…)。シンプルでわかりやすいアルゴリズムです。Rubyで書いて20数行だし。

#!/usr/bin/env ruby
# -*- ruby -*-

def merge(ary, ary1, ary2, &comp)
  comp = proc {|a1, a2| a1 < a2 } unless comp
  ary.size.times do |i|
    if ary1.first and ary2.first
      ary[i] = comp.call(ary1.first, ary2.first) ? ary1.shift : ary2.shift
    else
      ary[i] = ary1.first ? ary1.shift : ary2.shift
    end
  end
end

def merge_sort!(ary, &comp)
  return if ary.size < 2
  m = ary.size / 2
  n = ary.size - m
  ary1 = ary[0, m]
  ary2 = ary[m, n]
  merge_sort!(ary1, &comp)
  merge_sort!(ary2, &comp)
  merge(ary, ary1, ary2, &comp)
end

ary = [3, 2, 4, 1, 5, 0, 8, 6, 7, 9]
merge_sort!(ary)
p ary
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ary = [3, 2, 4, 1, 5, 0, 8, 6, 7, 9]
merge_sort!(ary) {|a1, a2| a1 > a2 }
p ary
# => [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]