CrystalでMerge Sort - ハイパーニートプログラマーへの道

Crystal 0.20.0

こちらのRuby versionを参考にしました。

def merge_sort(array)
  return array if array.size <= 1
  mid = (array.size / 2).round
  left, right = array[0...mid], array[mid..-1]
  merge(merge_sort(left), merge_sort(right))
end

def merge(left, right)
  res = [] of Int32
  until left.empty? || right.empty?
    if left.first <= right.first
      res.push(left.shift)
    else
      res.push(right.shift)
    end
  end
  res + left + right
end

もう一つ。上記のと変数名やメソッド名揃えてなくてアレですけど・・・。

これの元ネタはPython Algorithms, Listing 3-2

def mergesort2(seq)
  mid = (seq.size / 2).round
  lft, rgt = seq[0...mid], seq[mid..-1]
  lft = mergesort2(lft) if lft.size > 1
  rgt = mergesort2(rgt) if rgt.size > 1
  res = [] of Int32
  until lft.empty? || rgt.empty?
    if lft.first <= rgt.first
      res.push(lft.shift)
    else
      res.push(rgt.shift)
    end
  end
  return res + lft + rgt
end

crystal play上で実行してみます。

require "benchmark"
.
.
.
seq = [5,3,6,9,1,4,2,8,7]
Benchmark.bm do |x|
  x.report("merge_sort:") do
    p merge_sort(seq)
  end
  x.report("merge_sort2:") do
    p mergesort2(seq)
  end
end

                   user     system      total        real
merge_sort:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
  0.000000   0.010000   0.010000 (  0.014788)
merge_sort2: [1, 2, 3, 4, 5, 6, 7, 8, 9]
  0.000000   0.010000   0.010000 (  0.011958)