Insertion Sort

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.

ADS 03 N

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.

ADS 03 O

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:

ADS 03 PThis 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 [1].  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:

ADS 03 RNext: IS Pass 3