
The insertion sort, unlike the other sorts,
passes through the array only once.
The insertion sort is commonly compared to organizing a handful of
playing cards.
You pick up the random 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 subarrays. The first subarray (such as the cards in
your hand) is sorted and increases in size as the sort
continues. The second
subarray (such as the cards to be picked up) is unsorted, contains all the elements
to yet be inserted into the first
subarray, and decreases in size as the sort continues.
Let's look at our same example using the insertion sort for descending order.

Array at beginning: 
84 
69 
76 
86 
94 
91 

84 
69 
76 
86 
94 
91 

84 
69 
76 
86 
94 
91 

84 
76 
69 
86 
94 
91 

86 
84 
76 
69 
94 
91 

94 
86 
84 
76 
69 
91 
2nd subarray empty 
94 
91 
86 
84 
76 
69 
The insertion sort maintains the two
subarrays within the same array. At the beginning of the sort, the first
element in the first subarray is considered
the "sorted array". With each pass through the loop, the
next element in the unsorted second subarray is placed into its proper position in the
first sorted subarray.
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 InsertionSort( apvector <int> &num)
{
int i, j, key, numLength = num.length( );
for(j = 1; j < numLength; j++)
// Start with 1 (not 0)
{
key = num[j];
for(i = j  1; (i >= 0) && (num[i] < key); i)
// Smaller values move up
{
num[i+1] = num[i];
}
num[i+1] = key;
//Put key into its proper location
}
return;
}
