gistfile1.rb

# Mergesort
# precondition: no nils in the array
def sort some_array
  return some_array if some_array.length == 1

  half_length = some_array.length / 2
  first_half = sort(some_array[0,half_length])
  second_half = sort(some_array[half_length, some_array.length - half_length])

  result = []
  a = b = 0
  while a < first_half.length || b < second_half.length
    a_val = first_half[a]
    b_val = second_half[b]
    if b_val.nil? || (!a_val.nil? && a_val < b_val)
      result << a_val
      a += 1
    else
      result << b_val
      b += 1
    end
  end

  result
end