Insertion Sort

Insertion sort progressively sorts an array one value at a time to a new array until it is in order.

Here are the steps the algorithm follows:

1. Ignore the first value in the array (this should be moved over to the new array) and go straight to the second value.
2. Select the next value in the origianl array.
3. Place it in the correct place in the new array
4. Move onto the next value (three, four, five… and so on)
5. Repeat step 2 until the whole array is in order

Insertion sort is less efficient with larger lists than merge sort but more efficient than bubble sort. Insertion sort is more memory efficent than bubble sort and merge sort.