The insertion sort algorithm is the sort unknowingly used by most card
players when sorting the cards in their hands. When holding a hand of cards,
players will often scan their cards from left to right, looking for the first
card that is out of place. For example, if the first three cards of a
player's hand are 4, 5, 2, he will often be satisfied that the 4 and the 5
are in order relative to each other, but, upon getting to the 2, desires to
place it before the 4 and the 5. In that case, the player typically removes
the 2 from the list, shifts the 4 and the 5 one spot to the right, and then
places the 2 into the first slot on the left. This is insertion sort.
Unlike other simple sorts like selection sort and bubble sort which rely
primarily on comparing and swapping, the insertion sort achieves a sorted
data set by identifying an element that out of order relative to the elements
around it, removing it from the list, shifting elements up one place and
then placing the removed element in its correct location. Follow the step
by step process of sorting the following small list.

- (4) 3 1 2 --> The four is in the correct place relative to the
elements that have been
- considered to this point.
- (4 3) 1 2 --> The four and the three are incorrectly placed relative
to one another, so remove and shift
- (4 _) 1 2 --> Remove the 3 from the list
- (_ 4) 1 2 --> shift the four into the relative correct place
- (3 4) 1 2 --> Now the sublist that was being considered is in sorted order
- (3) 4 1 2 --> The three is in sorted order relative to the data before it
- (3 4) 1 2 --> The three and the four are in sorted order relative to the
data before it
- (3 4 1) 2 --> The 3, 4, and 1 are not in sorted order, so remove and shift
- (3 4 _) 2 --> Remove the 1
- (3 _ 4) 2 --> Shift the 4 up one place
- (_ 3 4) 2 --> Shift the 3 into its relatively correct place
- (1 3 4) 2 --> Place the one such that the sublist being considered is in
sorted order
- (1) 3 4 2 --> (1) is a sorted list
- (1 3) 4 2 --> (1 3) is a sorted list
- (1 3 4) 2 --> (1 3 4) is a sorted list
- (1 3 4 2) --> The two is out of order, so remove and shift
- (1 3 4 _) --> Remove the 2
- (1 3 _ 4) --> Shift the 4
- (1 _ 3 4) --> Shift the 3
- (1 2 3 4) --> Place the 2 into its correct place
- (1) 2 3 4 --> (1) is a sorted list
- (1 2) 3 4 --> (1 2) is a sorted list
- (1 2 3) 4 --> (1 2 3) is a sorted list
- (1 2 3 4) --> (1 2 3 4) is a sorted list, sort complete.

With a larger data set, it is even easier to see the sorted sublist growing
in size with each successive iteration. Note that after each iteration, the
size of the sorted data at the beginning of the list grows by one.

8 9 3 5 6 4 2 1 7 0

3 8 9 5 6 4 2 1 7 0

3 5 8 9 6 4 2 1 7 0

3 5 6 8 9 4 2 1 7 0

3 4 5 6 8 9 2 1 7 0

2 3 4 5 6 8 9 1 7 0

1 2 3 4 5 6 8 9 7 0

1 2 3 4 5 6 7 8 9 0

0 1 2 3 4 5 6 7 8 9