## The Insertion Sort

The insertion sort orders a list alphabetically or in order of size by picking the from the unsorted list and placing it in in alphabetical or numerical order in the ordered list as it is built up. This is repeated until all the elements in the unordered list have been transferred to the ordered list. The process is the way many people use to order a set of objects.

For example, to sort the list

4, 2, 5, 8, 1, 7, 9

The first number in the list is 4, so the ordered list starts with a 4:

4

The next number in the list is 2 and this is smaller than 4, so goes before it.

2, 4

The next number in the list is 5 and this is the largest number so far, and goes last.

2, 4, 5

The next number in the list is 5 so this is swapped with the fourth number to give the list

2, 4, 5, 8

The next number in the list is 1 and this is is the smallest of any so far and goes first.

1, 2, 4, 5, 8

The next is 7, and is placed in front of the 8.

1, 2, 4, 5, 7, 8

Finally, the 9 is placed last to give the ordered list

4, 2, 5, 8, 1, 7, 9