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
- 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