merge_sort.rb

# Merge sort implementation with extra space
def merge_sort(array)
  return array if array.size <= 1
  left = array[0...array.size / 2]
  right = array[array.size / 2...array.size]

  merge(merge_sort(left), merge_sort(right))
end
def merge(left, right)
  result = []

  while left.size > 0 && right.size > 0
    result << if left[0] <= right[0]
      left.shift
    else
      right.shift
    end
  end

  result.concat(left).concat(right)
end
merge_sort('MERGESORT'.chars)