The idea of swapping adjacent elements to sort a list of items can also be used to implement the insertion sort. In the insertion sort algorithm, we assume that a certain portion of the list has already been sorted, while the other portion remains unsorted. With this assumption, we move through the unsorted portion of the list, picking one element at a time. With this element, we go through the sorted portion of the list and insert it in the right order so that the sorted portion of the list remains sorted. That is a lot of grammar. Let's walk through the explanation with an example.
Consider the following array:
The algorithm starts by using a for loop to run between the indexes 1 and 4. We start from index 1 because we assume the sub-array with index 0 to already be in the sorted order:
At the start of the execution of the loop, we have the following:
...
