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.