Insertion Sort

The insertion sort, unlike the other sorts, passes through the array only once.  The insertion sort works much in the same way you organize a hand of cards. You pick up the unsorted cards one at a time.  As you pick up each card, you insert it into its correct position in your hand of organized cards.  The insertion sort splits an array into two sub-arrays. The first sub-array is always sorted and gets larger as the sort continues. The second sub-array is unsorted and contains all the elements not yet inserted into the first sub-array. The second sub-array gets smaller as the sort progresses. Let's look at our same example using the insertion sort for descending order.

  The insertion sort algorithm maintains the two sub-arrays within the same array.  When the sort first begins, the first element in the array is considered to be the "sorted array".  With each iteration of the loop, the next value in the unsorted section is placed into its proper position in the sorted section.

The insertion sort can be very fast and efficient when used with smaller arrays.  Unfortunately, it loses this efficiency when dealing with large amounts of data.

// Insertion Sort Function for Descending Order
void insertion_sort( apvector <int> &array)
{
     int i, j, key, array_length=array.length( );
     for(j = 1; j < array_length; j++)    //Notice starting with 1 (not 0)
    {
           key = array[j];
           for(i = j - 1; (i >= 0) && (array[i] < key); i--)   //Move smaller values up one position
          {
                 array[i+1] = array[i];
          }
         array[i+1] = key;    //Insert key into proper position
     }
     return;
}