def insert(L, b):
    # insert L[b] where it belongs in L[0:b+1]
    # L[0:b-1] must already be in sorted order
    i = b
    while i != 0 and L[i-1] >= L[b]:
        i = i - 1
    
    value = L.pop(b)     # remove b from current position
    L.insert(i,value)    # insert value at ith position
    
def insertion_sort(L):
    i = 1
    while i != len(L):
        insert(L,i)
        i = i + 1