#配列Aの要素iを挿入する
#区間[0, i)は昇順に整列されている
insertion(A, i):
    j ← i - 1
    t ← A[i]

    while True:
        if j < 0:
            break
        if !(j ≥ 0 and A[j] > t):
            break
        A[j+1] ← A[j]
        j ← j - 1

    A[j+1] ← t