Collin Anderson

Insertion Sort takes each element, and inserts it into the correct part of the list. It divides the list into a sorted part and a not sorted part. In the beginning the entire list is considered unsorted, and in the end the entire list is sorted.

def insertsort(lst):
    for x in range(len(lst)): #for each element
        for y in range(x, 0, -1): #go back through the sorted section of the list
            if lst[y - 1] > lst[y]: #if the y is greater than the previous
                swap(lst, y - 1, y) #swap the two

Here is a version that picks up an element and shifts the others over instead of swapping each element.

def insertsort2(lst):
    for x in range(len(lst)): #for each element
        el = lst[x] #pick up the element
        while x > 0 and el < lst[x - 1]:
            lst[x] = lst[x - 1]
            #here x actually goes to zero, but the range function will still give the next correct value
            x -= 1
        lst[x] = el #drop the element