http://codezine.jp/article/detail/2886 のプログラムをRubyに移植しました

msort.rb

#!ruby

# http://codezine.jp/article/detail/2886 のプログラムをRubyに移植しました

def main
  merge_sort "input.txt", "result.txt"
end

def merge_sort(in_path, out_path)
  open_multi([in_path, "rb"], [out_path, "wb"]) do |rf, wf|
    rf.each_line.each_slice(1000000) do |lines|
      #lines = lines.sort
      wf.write lines.join("")
    end
  end
  tmp_path1, tmp_path2 = "tmp1.txt", "tmp2.txt"
  
  begin
    divide out_path, tmp_path1, tmp_path2
    run_count = merge(out_path, tmp_path1, tmp_path2)
    puts "run_count = #{run_count}"
  end until run_count == 1
  File.delete(tmp_path1)
  File.delete(tmp_path2)
end

def divide(out_path, tmp_path1, tmp_path2)
  open_multi([out_path, "rb"], [tmp_path1, "wb"], [tmp_path2, "wb"]) do |rf, wf1, wf2|
    reader = StringQueReader.new(rf)
    while true
      break unless reader.available?
      reader.copy_run_to wf1
      break unless reader.available?
      reader.copy_run_to wf2
    end
  end
end

def merge(out_path, tmp_path1, tmp_path2)
  run_count = 0
  open_multi([tmp_path1, "rb"], [tmp_path2, "rb"], [out_path, "wb"]) do |rf1, rf2, wf|
    reader1 = StringQueReader.new(rf1)
    reader2 = StringQueReader.new(rf2)
    # reader1,2共に空でない間
    while reader1.available? and reader2.available?
      while true
        if compare(reader1.current, reader2.current) < 0
          a, b = reader1, reader2
        else
          a, b = reader2, reader1
        end
        a.copy_to wf
        if a.end_of_run?
          b.copy_run_to wf
          break
        end
      end
      run_count += 1
    end
    [reader1, reader2].each do |r|
      while r.available?
        r.copy_run_to wf
        run_count += 1
      end
    end
  end
  run_count
end

def compare(line1, line2)
  line1 <=> line2
end

def open_multi(*args)
  ios = []
  args.each {|(path,mode)| ios << open(path, mode) }
  yield *ios
ensure
  ios.each {|f| f.close }
end

class StringQueReader
  def initialize(io)
    @io = io
    @last = nil
    @current = nil
    read_next()
  end
  
  attr_reader :current
  
  def read_next()
    @last = @current
    @current = @io.gets
  end
  
  def available?
    @current != nil
  end
  
  def end_of_run?
    @current == nil or compare(@current, @last) < 0
  end
  
  def copy_to(output)
    output.puts @current
    read_next()
  end
  
  def copy_run_to(output)
    begin
      copy_to output
    end until end_of_run?
  end
end

if $0 == __FILE__
  main()
end