Merge Sort

gistfile1.txt

andersonvom /tmp/sort $ wc -l random.txt
1241894 random.txt

andersonvom /tmp/sort $ time ruby merge_sort.rb

real    0m21.932s
user    0m21.730s
sys     0m0.200s

merge_sort.rb

input = "random.txt"
output = "ordered.txt"
numbers = []

def merge_sort(arr)

  size = arr.size

  return arr if size <= 1
  if size == 2
    return arr if (arr[0] <=> arr[1]) < 1
    return arr.reverse
  end

  half = size / 2
  arr1 = merge_sort arr[0..half]
  arr2 = merge_sort arr[(half+1)..-1]
  arr_sort = []

  e1 = arr1.shift
  e2 = arr2.shift
  while (e1 and e2)
    if (e1<=>e2) < 1
      arr_sort << e1
      e1 = arr1.shift
    else
      arr_sort << e2
      e2 = arr2.shift
    end
  end

  arr_sort << (e1 || e2)
  arr_sort += arr1
  arr_sort += arr2

end

if __FILE__ == $0
  File.open(input, 'r') do |f|
    while (line = f.gets)
      numbers << line
    end
  end
  output_numbers = merge_sort numbers

  File.open(output, 'w') do |f|
    f.write(output_numbers)
  end
end