From the clrs book, why does insert insertion sort for a loop repeat n times?

Question

Why is the first line repeated n times when it starts at 2? Shouldn't it be n-1? Also why line 2 and 3 is n-1 and not n?

Answer 1

Here, the loop statement is considered executed again, because it compared both before the first iteration and after the last iteration. Let’s take a look A.length = 3. We have only two iterations, but three comparisons:

j := 2
if j > A.length then exit the loop // first comparison, false
... first loop iteration goes

j := j + 1 // j = 3 now
if j > A.length then exit the loop // second comparison, false
... second loop iteration goes

j := j + 1 // j = 4 now
if j > A.length then exit the loop // third comparison, true

, , , . , A.length = 1, .