insertion_sort(A,n)
  for i = 2 to n
    key = A[i]
    // Insert A[i] into the sorted subarray A[1:i-1].
    j = i - 1
    while j > 0 and A[j] > key
      A[j + 1] = A[j]
      j = j - 1
    A[j + 1] = key