某クロッシング問題をmerge sortで解いてみた: ( https://codeiq.jp/ace/yuki_hiroshi/q432 )

merge_sort-crossing.rb

#!/usr/env/ruby -v

require 'benchmark'
measure = Benchmark.measure {
  @crossing_count = 0

  def merge(a, b)
    sorted = []
    until (a.empty? || b.empty?)
      if a.first < b.first
        sorted << a.shift
      else
        @crossing_count += a.size
        sorted << b.shift
      end
    end
    sorted += a + b
  end

  def merge_sort(array)
    return array if array.size == 1
    center = array.size / 2
    a = merge_sort(array[0...center])
    b = merge_sort(array[center..-1])
    merge(a, b)
  end

  INPUT = 'crossing.txt'

  rays = []
  open(INPUT).read.each_line { |line|
    rays << line.chomp.to_i
  }

  merge_sort(rays)
  p @crossing_count 
}
puts Benchmark::CAPTION
puts measure #=> 1.4秒ぐらい