shellSort(A, N):
    interval ← {5, 3, 1}

    for g in interval:
        insertionSort(A, N, g)

# 間隔gを指定した挿入ソート
insertionSort(A, N, g):
    for i ← g to N-1:
        t ← A[i]
        j ← i - g

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

        A[j+g] ← t