Insertion Sort

1. This is like ordering cards - left hand has a sorted set of cards; you take a card from an unsorted deck, insert it in the correct sorted position among the cards in the left hand, and keep on doing this. Eventually your left hand will have all cards sorted. Note that the original subscripts, indicating relative positions of the items, are re-arranged after sorting. So in the figure below, a₀, ...., a_j-1, are not the original a₀, ...., a_j-1.

/* Insertion sort for integers */

void insertion( int a[], int n ) {
/* Pre-condition: a contains n items to be sorted */
    int i, j, v;
    /* Initially, the first item is considered 'sorted' */
    /* i divides a into a sorted region, x<i, and an
       unsorted one, x >= i */
    for(i=1;i<n;i++) {
        /* Select the item at the beginning of the
           as yet unsorted section */
        v = a[i];
        /* Work backwards through the array, finding where v 
           should go */
        j = i;
        /* If this element is greater than v,
              move it up one */
        while ( a[j-1] > v ) {
          a[j] = a[j-1]; j = j-1;
          if ( j <= 0 ) break;
          }
        /* Stopped when a[j-1] <= v, so put v at position j */
        a[j] = v;
        }
    }