insertion_sort.rb

def insertion_sort(array)
  n = 1
  while n < array.length
    key = array[n]
    i = n - 1
    while i >= 0 and array[i] > key
      array[i + 1] = array[i]
      i = i - 1
    end
    array[i + 1] = key
    n = n + 1
  end
  return array
end