sri ramanuja seva

(In the previous series of posts on Insertion Sort, we looked at the working of the algorithm on simple example, and also analysed its running time.)

Some more details about Insertion Sort

• It is an in-place sorting algorithm, (That is, we don’t create a new temporary array, or anything like that. We rearrange the elements within the same input array itself, and use only O(1) extra space.)
• It is a stable sorting algorithm. (That is, the relative order of equal elements is maintained in the sorted array.) (This is because, in any pass, we shift an element to the right (and bring the key to the left) only if the key is smaller than that element. If the key is equal value, we leave the key there itself. We don’t do any further shifting or rearranging in that pass.)
• When is Insertion Sort useful? Answer: When the array size is fairly small, or when the array is already almost sorted.

---

Pseudo-code for Insertion Sort

Input: Array A [1 … n] having n elements indexed from 1 to n.
Output: Sorted Array A .

Algorithm:

//there are n-1 passes in all 
For index i going from 2 up to n: 
          key <-- A[i]. // set the key in each pass. 
          // compare key backwards and insert at appropriate position. 
          // compare as long as key is smaller, or until we reach the 
          // very beginning of the array. 
          j <- (i-1).
          while (j >= 1) AND (key < A[j])
                        A[j+1] <- A[j] //shift A[j] to the right. 
                        j <- (j-1)     //go backward. 
         //we've found appropriate position to insert the key. Insert it. 
         A[j+1] <- key. 

Above is the pseudo-code for Insertion Sort. This is the same algorithm that we had explained in text earlier, and looked at examples for.
One subtle point:
In the while condition:
We’ve written: while (j >= 1) AND (key < A[j])
What if we instead wrote:
while (key < A[j]) AND (j >= 1)
This 2nd version could potentially create problems. Because it may try to check the value of A[j] even at an index that is non-existent. So, it is proper to first check the index and then do the key value comparison.