Insertion Sort
The insertion sort uses the principle of a marker moving along a list with a sorted side to the left side of the marker and the unsorted side to the right of the marker.
The list of steps is as follows:
This video tutorial from Virginia Tech shows this being demonstrated using a set of cards.
Here is the algorithm for the insertion sort:
1 2 3 4 5 6 7 8 9 10 11 

Exercises
 Implement the insertion sort using the algorithm above as a guide. Test that it works with an unsorted list
 Add a counter to report how many comparisons have been done during the sorting process.
 Compare the number of comparisons for the insertion sort with the bubble sort
 Previous  Bubble Sort
 Next  Quicksort