Take 10 number cards of the same suit from a standard deck of playing cards and shuffle them into a random order.  Hold the randomised cards as a fan in one hand.

Keeping hold of the cards, arrange them into ascending numerical order as shown here:

You have probably just performed an Insertion Sort, or something close to it.

Perform an insertion sort

Let’s sort a few cards again in the same way, one step at a time (without some of the shortcuts you took last time).  Lay the following cards in front of you as shown:

This represents an unsorted array of numbers that a program would have to sort.

To begin the sort, divide the sorted and unsorted sections of the list by placing a pointer after the first number.  The sorted section will be on the left and the unsorted section will be on the right.  To sort the numbers, you will repeatedly compare the first unsorted number with the numbers in the sorted section.  If the unsorted number is smaller than its sorted neighbour, you will swap them.

The first number in the unsorted section is 8, so compare it with the number to the left. Since 8 is greater than 7, these numbers do not need to be swapped.  Simply advance the pointer one position.  Notice that only one comparison was needed to sort the 8.

Now the first number in the unsorted section is 5.  Because 5 is less than 8, we need to swap these numbers.

But 5 is also less than 7, so swap these numbers as well.

This time two comparisons and two swaps were needed to sort the number 5.  Now 5 is in the correct order, so advance the pointer one position.

Now the first number in the unsorted section is 2.  Because 2 is less than 8, we need to swap it with 8.  Because 2 is less than 7, we swap it with 7.  And because 2 is less than 5, we swap it with 5.  We needed three comparisons and three swaps to get 2 into the correct sorted position.  Now we can advance the pointer.

Now the first number in the unsorted section is 4.  Because 4 is less than 8, we need to swap it with 8.  Because 4 is less than 7, we need to swap it with 7.  And because 4 is less than 5, we need to swap it with 5.  Finally we compare the 4 with 2 but find that we do not need to swap.  This time we needed four comparisons and three swaps to put the 4 in the correct order.  Now we can advance the pointer.

Now 6 is the first number in the unsorted section.  After three comparisons and two swaps, we can place 6 in the correct position between 5 and 7.  Notice that we did not need to compare the 6 with the 2 or the 4 since we already know these numbers are less than 5.  Once we finds a number in the sorted section less than 6, we know we have found the correct position for 6 and can advance the pointer.  If you think about this, you will agree that there is potentially less work to do than with a bubble sort.

The final unsorted number is 3.  To find the correct position for 3, we must compare it with every number in the unsorted section.  However, only five swaps are required since the first number (2) is less than 3.  After moving 3 to the correct position and advancing the sort marker, the Insertion Sort is complete since the unsorted section is empty.

Ask someone else to shuffle all of your cards (1 to 10), lay them out in front of you, and perform an insertion sort with them using the same technique as illustrated above. Use a strip of scrap paper as a pointer.

Do this again, until you are happy with the process.

Insertion Sort Algorithm

As you have seen, the insertion sort pointer begins its travels immediately after the first value in the list.  This pointer separates the sorted section of the list on its left hand side from the unsorted section on its right.  The first item in the unsorted section becomes the current item which is compared with the item on its left.  If necessary, the current item is swapped with the item on its left.  The current item is then compared the next item it finds to the left of itself, and they are swapped if necessary. This continues until the current item arrives at the correct position and no more swaps are needed.  Then the pointer advances and a new current item is selected.  The whole process continues until the pointer has nowhere else to go.  This algorithm can be described as show here.

You can see a nice animation of an insertion sort here:

http://www.ee.ryerson.ca/~courses/coe428/sorting/insertionsort.html

Insertion sort pseudo-code

Here is some pseudocode for sorting an array into ascending order. It assumes we are using a 0 based array, which is typical – so the initial pointer value of 1 means it’s pointing to second item in the array to begin with, and the outer for loop will run for the length of the array, that is the number of items in the array,  – 1 times. The item in the array given by the value of the pointer becomes the current item.  We have another variable called position which tracks the position of the current item as it moves towards the left following successive swaps. Each swap is achieved by means of a temporary variable (in a similar way to that used in a bubble sort). The value of position is reduced by 1 each time a swap is made, allowing the current item to be compared with the next item on its left. The inner loop will exit as soon there is no need for another swap, or position becomes zero because the current item was the smallest of all so far.

 

For pointer = 1 to Array.Length – 1

      currentItem = Array(pointer)

      position = pointer

      While position > 0  AND Array(position – 1 ) > currentItem

            Temp = Array(position)

            Array(position)  = Array(position – 1)

            Array(position – 1) = Temp

            position = position – 1   

      End While

Next pointer