Why does my insertion sort Algorithm return out of order

Question

I am working on creating a basic insertion sort algorithm using Python.

My textbook shows the psudeocode of an insertion sort algorithm here.

If I follow that convention using python 3, I produce the following code:

def insertionSort(arr):
#Traverse through 1 to len array
   for j in range(1, len(arr)):
       key = arr[j]
       i = j-1
       while i >0 and arr[i] > key:  #this line seems incorrect?
           arr[i+1] = arr[i]
           i = i-1
       arr[i+1] = key
   return arr

If I set arr = [12,11,13,5,6] The result returns as [12,5,6,11,12,13] which obviously is not a correct sort.

After tweaking with the algorithm for some time changing the line I marked as incorrect to while i>=0 and arr[i] > key: the algorithm gives the correct output. Is my book incorrect in omitting the equal sign or am I not understanding how the psuedocode operates within my textbook?

Answer 1

It looks like you mostly correctly translated the book's algorithm into Python. As you see, the book's algorithm is 1-based while Python is 0-based.

The book's algorithm starts at index 2 but you have to start at index 1.

This also translates to keeping the while loop going until the first index. In the book's case, that's 1 and in your case it should be 0 in Python. So the book is correct but you are also correct (because of the differences in indexing conventions).