# coding=utf-8

# sortowanie przez wstawianie
def insertion_sort(v):

    # niezmiennik: przed każdym obrotem pętli, fragment od 0 do i jest posortowany
    for i in range(1, len(v)):
        # znajdź pierwszy element większy od v[i] we fragmencie v od 0 do i
        j = 0
        while v[j] <= v[i] and j < i:
            j += 1
        
        # zapamiętaj na boku element v[i]
        tmp = v[i]

        # przesuń fragment od j do i - 1 o jeden element w prawo (żeby zrobić miejsce na pozycji j dla elementu v[i])
        # zakres [::-1] odwraca listę
        for k in range(j + 1, i + 1)[::-1]:
            v[k] = v[k - 1]

        # wstaw element i na właściwe miejsce
        v[j] = tmp

        print v

    # warunek końcowy: i == len(v) - 1, fragment od 0 do len(v) - 1 jest posortowany,
    # czyli cała lista v jest posortowana