insertion_sort.py

def insertion_sort(seq):
    for i in range(1, len(seq)):
        key = seq[i];
        left = i - 1;

        while left >= 0 and seq[left] > key:
            seq[left + 1] = seq[left]
            seq[left] = key
            left -= 1
    return seq