merge.rb

#!/usr/bin/env ruby

def merge_sort(array)
  return array if array.length <= 1

  mid = array.size / 2
  left = array[0..mid]
  right = array[mid+1..-1]

  s_left = merge_sort(left)
  s_right = merge_sort(right)

  i = 0
  j = 0
  ret = []
  loop do
    break unless i < s_left.length
    break unless j < s_right.length

    if s_left[i] < s_right[j]
      ret << s_left[i]
      i += 1
    else
      ret << s_right[j]
      j += 1
    end
  end

  if i == s_left.length - 1
    ret += s_right
  else
    ret += s_left
  end
  ret
end

t = [3, 4, 5, 6, 7, 1]

p merge_sort(t)