data = [80, 57, 121, 26, 93, 172, 107, 36, 88, 64, 67, 124, 7, 20, 53, 154, 196, 29, 82, 34, 142, 110,
           159, 17, 192, 46, 65, 115, 162, 184, 168, 102, 35, 19, 23, 70, 163, 166, 187, 129, 90, 193, 143, 167,
           119, 95, 89, 58, 178, 71]

def insertion_sort(data)
  n = data.length
  k = 1
  while k < n
    cur = data[k]
    j = k
    while j > 0 && data[j - 1] > cur
      data[j] = data[j - 1]
      j -= 1
    end
    data[j] = cur
    k += 1
  end
  puts data
end

insertion_sort(data)