def insertion_sort(array)
  (array.size).times do |n|
    while n > 0
      if array[n - 1] > array[n]
        array[n], array[n - 1] = array[n - 1], array[n]
      else
        break
      end
      n -= 1
    end
  end
  return array
end

array = [18, 5, 20, 8, 5, 12, 1, 0, 5]
p insertion_sort(array)