In [1]:

    

def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        while j > 0 and a[j-1] > a[j]:
            a[j-1], a[j] = a[j], a[j-1]
            j -= 1
    return a


    

In [25]:

    

def insertion_sort2(a):
    for i in range(len(a)):
        for j in range(i, 0, -1): # or use reversed(range(1, i+1))
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
            else:
                break
                
    return a


    

In [31]:

    

# use cache for current value
def insertion_sort3(a):
    
    for i in range(1, len(a)):
        current_val = a[i]
        j = i
        while j > 0 and a[j-1] > current_val:
            a[j] = a[j-1]
            j -= 1
        a[j] = current_val
    return a


    

In [2]:

    

alist = [34,2,24,12, 45,33,9,99]
print(insertion_sort(alist))


    

    




[2, 9, 12, 24, 33, 34, 45, 99]

In [35]:

    

insertion_sort(alist)


    

    
Out[35]:





[2, 9, 12, 24, 33, 34, 45, 99]

In [37]:

    

alist = [34,2,24,12,30, 45,33,9,99]
#print(insertion_sort(alist))


    

In [38]:

    

insertion_sort(alist)


    

    
Out[38]:





[2, 9, 12, 24, 30, 33, 34, 45, 99]

In [39]:

    

alist = [34,2,2,24,12, 45,33,9,99]
#print(insertion_sort(alist))


    

In [40]:

    

insertion_sort3(alist)


    

    
Out[40]:





[2, 2, 9, 12, 24, 33, 34, 45, 99]

In [ ]:

    




    

In [ ]: