def insertion_sort(L):
    for i in range(1,len(L)):                   # 5 steps
        current_val = L[i]                      # 3 steps
        j = i                                   # 2 steps
        while(j > 0 and L[j-1] < current_val):  # 8 steps
            L[j] = L[j-1]                       # 5 steps
            j = j -1                            # 3 steps
        L[j] = current_val                      # 3 steps
        
        #worst case analysis
        # steps 5-8 may happen up to n times (8 + 5 + 3 + 3) * n = 19n
        # steps 1-3 + 5-8 may happen up to n times (5 + 3 + 2 + 19n) * n = 10n + 19n^2
        # T(n) = 19n^2 + 10n
        
if(__name__ == "__main__"):
    L = [5, 7, 1, 9, 3, 2, 0, 4, 6, 8]
    insertion_sort(L)
    print(L)