マージソートとクイックソートの比較（Ruby）

自分の実装で、マージソートとクイックソートのベンチマークをしてみました。
マージソートの実装はこれ、クイックソートのはこれ（いちばん下の実装）です。
　
マージソート。

クイックソート。

基本的にクイックソートの方が速いようである。

ベンチマーク。
bench_sorts.rb

require 'benchmark'

100.times do
  ar = (0..10_0000).to_a.shuffle
  Benchmark.bm 12 do |x|
    x.report("merge sort") {ar.merge_sort}
    x.report("quick sort") {ar.qsort}
  end
end

実行は $ ruby bench_sorts.rb > bench_sorts.txt。

Gnuplot でグラフ化。

require 'histogram/array'
require 'numo/gnuplot'

ar = open("bench_sorts.txt", &:readlines)
m = []
q = []
ar.each_slice(3) {|x| m << x[1]; q << x[2]}

pick_up = proc do |ar|
  ar.each_with_object([]) {|i, a| a << i.split(" ")[6].to_f}
end

mb, mf = pick_up.call(m).histogram
qb, qf = pick_up.call(q).histogram

Numo.gnuplot do
  set title: "merge sort"
  set terminal: [png: {size: [400, 300]}]
  set output: 'sort_m.png'
  set style: [:fill, :solid, {border: -1}]
  plot mb, mf, w: :boxes, lc: {rgb: "orange"}
end

Numo.gnuplot do
  set title: "quick sort"
  set terminal: [png: {size: [400, 300]}]
  set output: 'sort_q.png'
  set style: [:fill, :solid, {border: -1}]
  plot qb, qf, w: :boxes, lc: {rgb: "orange"}
end