InsertionSort

In most cases, InsertionSort is the best of the simple sorts (i.e. BubbleSort, ExchangeSort, and SelectionSort).

InsertionSort works well if only a few elements need sorting; however, it is a poor choice if dealing with a large number of elements.

Often times InsertionSort is used as the final stage of more advanced sorts (e.g. QuickSort).

For an example of InsertionSort, assume we have an array A and its length is N. Let's look at pass i (1 <= i <= N-1). The sublist A[0] to A[i-1] is already sorted in ascending order. The pass assigns A[i] to the list. Let A[i] be the TARGET and move down the list, comparing the target with items A[i-1], A[i-2], and so forth. Stop the scan at the first element A[j] that is less than or equal to TARGET or at the beginning of the list (j=0). As we move down the list, slide each element to the right (A[j]=A[j-1]). When the correct location for A[i] is found, insert it at location j.

Said another way.

Assume elements are being collected using array named 'a'. The initial state is that the first element, considered by itself, is sorted. Each time a new element with value 'n' is "added" to the collection, it is inserted into a slot 'i' such that a[i-1] <= a[i] <= a[i+1]. If the new element is inserted into the array (i.e. it is not the last element), then the elements to the right of the insertion point must be shifted.

Many card players use the insertion sort. They are dealt a hand of cards. Each time they receive a card they place it in their hand in a sorted order. Luckily for them, shifting cards is simple. The following is an example of a card player that stores their cards in ascending order (lowest-to-highest).

   start with an empty hand
   receive an 8:  8                 //1 element is always sorted
   receive a  4:  4 8               //4 is inserted, the 8 was shifted
   receive a 10:  4 8 10            //10 added (no shifting necessary)
   receive a  2:  2 4 8 10          //4,8,10 all shifted
   receive a  7:  2 4 7 8 10        //8,10 shifted

InsertionSort pseudo-code.

   // assume we have an array 'a' with 'n' elements

   for (cur_i = 1; cur_i < n; cur_i++) {
      next_i = cur_i;
      while (next_i > 0) {
         if (COMPARE (a, next_i, next_i-1))
            SWAP (a, next_i, next_i-1);
         next_i--;
      }
   }

YouTube.com::Insertion Sort by CS50 at Harvard