insertion sort

Insertion Sort works by growing a sorted array out of the given unsorted array:

1. consider the first element sorted already, since it has no one to compare with yet.
2. compare the second element with the first element; if the second is smaller than the first, swap them - now we get a sorted array of two elements.
3. compare the third element to the elements to its left; whenever it meets a smaller element, swap the elements being compared - now we get a sorted array of three elements.
4. repeat the same steps for all the remaining elements: compare an element with all the sorted elements to its left: whenever it meets a smaller element, swap them.
5. when you reach the end of the array, you are done. Now all the elements are sorted.