# 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 Procedure InsertionSort (List, First, Last) For CurrentPointer <- First + 1 To Last CurrentValue <- List[CurrentPointer] Pointer <- CurrentPointer − 1 While List[Pointer] > CurrentValue AND Pointer > 0 List[Pointer+1] <- List[Pointer] Pointer <- Pointer − 1 EndWhile List[Pointer+1] <- CurrentValue EndFor EndProcedure 

## Exercises

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

by Sue Sentance.
01 November 2012.
updated on 01 November 2012.