Concerning the code for insertion sort

Question

I am currently reading Introduction to Algorithms by Cormen and co. I have some trouble deducing the pseudo-code for it. I understand what the algorithm does intuitively and how certain elements are sorted in a array of integers. For instance array = [5][2][4][6][1][3], the key is j=2, and i = j-1. It then checks is i > 0 and [5] then swaps [2] with [5]. Here comes the confusing part: i = i -1?? I mean we just set i = j-1, and why are we decreamenting i again?

Here is the following pseudo-code:

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
          A[i + 1] = A[i]
          i = i - 1         //this the part I do not understand.
    A[i + 1] = key

Answer 1

The insertion outlined here does the following:

At each j, the part of the array before index j is sorted and after index j is not sorted.

So the insertion sort finds a suitable place for the new A[j] and inserts it there.

For example, at j = 4 and i = 3 if the array is

2 4 5 3 1 0  
      ^

The array before element 3 is sorted.  
1. So it checks that 3 is less than 5, hence copies 5 to array[i+1] (i+1 = 4).  
   2 4 5 5 1 0  
2. Then it decrements i checks that 3 is less than 4, hence copies 4 to array[i+1] (i+1 = 3).  
   2 4 4 5 1 0   
3. Then it checks that 3 is more than 2, hence stops and makes A[i+1] = key.  
   2 3 4 5 1 0   

Answer 2

The array elements 1..(j-1) are already sorted and you try to insert the element a[j] into the sorted elements. This is done by the while loop. Starting with element a[j-1] the new element a[j] is compared with the already sorted elements one by one until the proper insertion place is found. As long as a[i] is larger, a[j] must go before that element so we move up a[i] by one place and reduce i in order to come to the next element to compare.

To understand the algorithm, I suggest you make a desk check with a small example. Follow all the steps and see how it behaves.