# 在数组 A 中插入元素 i（第 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