merge_sort.rb

#!/usr/bin/env ruby

# MergeSort

def merge_sort(arr)
  return arr if arr.size == 1
  lhs = merge_sort( arr.first(arr.size / 2) )
  rhs = merge_sort( arr.last(arr.size - arr.size / 2) )
  arr_new = []
  until( lhs.empty? || rhs.empty? ) do
    arr_new << ( lhs.first <= rhs.first ? lhs.shift : rhs.shift )
  end
  arr_new += lhs + rhs
end

arr = []
1..10.times do
  arr << rand(100)
end

p arr
p merge_sort(arr)