An insertion sort is a multi-pass sort where elements are put into place by identifying the place to create a gap in a sorted sequence and inserting the item into that gap. Consider the following data set. It is not in sorted order – we wish to sort it using insertion sort.
IS Pass 1
Consider the first two data items. They are out of order relative to each other, so we remove the second item from the array (by copying into a temporary variable) and slide the 35 value to the right. This will create a gap at location 0, and we can insert 19 into the gap. This results in the first two values being sorted relative to each other.
IS Pass 2
Now that the first two values are sorted relative to each other we can now apply the process to the first three data items:
This time we remove the third item from the array, and compare it with the data items in the already sorted section. As 35 > 24 we move the 35 one slot to the right. This moves the gap to element . We next compare 24 to 19, and discover that 24> 19. This means that the gap is in the correct place, and we can move 24 into the gap:
Next: IS Pass 3