insertion_sort.py

def insertion_sort(lst):
    i = 1
    
    # invarient:
    # We keep the left part of the list sorted:
    # [ ..sorted.. i ..unsorted.. ]
    while i < len(lst):
        # "target" is the item that we want to
        # insert back to the left sorted part
        # for example:
        # [4, 5, 7, 9, 6, 3, 1, 2]
        #              ^
        #              |
        #              i (target)
        target = lst[i]

        # shift everything > target right by 1 offset
        # for the same example
        # [4, 5, x, 7, 9, 3, 1, 2]
        #     ^  ^     ^
        #     |  |     |
        #     j  x     i
        j = i - 1
        while j >= 0:
            if lst[j] > target:
                # shift everything > target right by 1 offset
                lst[j+1] = lst[j]
                j -= 1
            else:
                break

        # save target back at the position x, which is j + 1
        lst[j+1] = target
        i += 1
        # Now the list looks like:
        # [4, 5, 6, 7, 9, 3, 1, 2]
        #                 ^
        #                 |
        #               next i
lst = [3,2,2,4,5,6,7,9,9,6,4,2,1]
insertion_sort(lst)
print(lst)