insertion sort does not order array correctly

Here is my insertion sort, exactly the way it is in the book "introduction to algorithms":

def insertion_sort():
    A = [5,2,4,6,1,3]
    for j in range(1, len(A)):
        print 'j:'+str(j)
        key = A[j]
        print 'key:'+str(key)
        i=j-1
        print 'i:'+str(i)
        while i > 0 and A[i] > key:
            A[i+1] = A[i]
            i=i-1
            print 'new i: '+str(i)
        print 'swapping value: '+str(A[i]) + ' with value: '+str(A[i+1])
        print ' '
        A[i+1] = key
    print A

This prints:

[5, 1, 2, 3, 4, 6]

What am I doing wrong to have them out of order?

In Introduction to Algorithms, they always assume arrays start at index 1, so you are starting your range() at 1, but python lists are 0-based indexed. This means you are never comparing 5, which is at A[0]. Notice everything after 5 is sorted.

modifying your for loop to -

for j in range(0, len(A)):

and your while condition to

while i >= 0 and A[i] > key:

Should do the trick.