Insertion Sort

insertionsort.py

#!/usr/bin/env python
'''
Insertion sort
 - Best:    O(n)
 - Average: O(n^2)
 - Worst:   O(n^2)
'''

def insertionsort(l):
    for i in xrange(0, len(l)):
        val = l[i]
        j = i - 1 

        # The invariant is that items to the left of l[i] are sorted.
        # Because of that, we can move left until we find the first 
        # item that is smaller than val, and insert after it.
        while j >= 0 and l[j] > val:
            l[j + 1] = l[j]
            j -= 1

        l[j + 1] = val 

if __name__ == "__main__":
    l = [3, 1, 10, 7, 8, 5, 6, 2]

    insertionsort(l)

    print l