Clarification on output of insertion sort implementation

Question

I was hoping for a clarification on the insertion sort algorithm implemented in Python. I am implementing the algorithm using this pseudo-code as a guide:

Using the implementation exactly as below (replacing index 2 in for loop for python index starting at 0):

l = [31, 41, 59, 26, 41, 58]
for j in range(1, len(l)):
    key = l[j]
    i = j - 1
    while i > 0 and l[i] > key:
        l[i+1] = l[i]
        i = i - 1
    l[i+1] = key

print(l)

>> [31, 26, 41, 41, 58, 59]

As you can see it sorted all values other than the value at position zero in the list.

However if I alter the index conditional in the while loop from i > 0 to i >= 0 the list is ordered correctly on output:

l = [31, 41, 59, 26, 41, 58]
for j in range(1, len(l)):
    key = l[j]
    i = j - 1
    while i >= 0 and l[i] > key:
        l[i+1] = l[i]
        i = i - 1
    l[i+1] = key


print(l)
>> [26, 31, 41, 41, 58, 59]

Could someone please clarify why this is the case?

Answer 1

You remembered to subtract 1 from the index because Python's lists are zero-based in for j. You forgot to do the same in while i > 0. Replacing while i > 0 to while i >= 0 is the same as while i > -1