アルゴリズムクイックリファレンス：挿入ソート

insertion_sort.py

def insertion_sort(target):
    for i in range(len(target)):
        insert(target, i, target[i])


def insert(target, pos, value):
    i = pos - 1
    while (i >= 0 and target[i] > value):
        target[i + 1] = target[i]
        i = i - 1
    target[i + 1] = value