# 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

- 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