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.

Array at beginning:
84 69 76 86 94 91
1st and, 2nd sub-array
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

94 91 86 84 76 69, 2nd sub-array empty

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 Method for Descending Order

public static void insertion_sort( int [ ] array)

{

     int j;  // the number of items sorted so far

     int key;  // the item to be inserted

     int i;  

     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

     }

}