In this lesson, we explain and demonstrate the insertion sort algorithm. Like the previous bubblesort, the insertion sort compares adjacent elements and swaps them if they are out of order. However, the insertion sort gains some added efficiency by maintaining a sorted list that we insert elements into.

Above, we show a typical stage of the insertion sort algorithm. The first four elements have already been sorted. The fifth element, 7, is being inserted into the sorted list. After the next comparison and swap, the array looks like this.

Continuing with the insertion of this element. We make comparisons with each of the elements in front of the 7 and swap them if they are out of order. In this particular insertion, the 7 moves all the way to the front of the array. However, if the 7 were larger than some of the other elements we would make fewer comparisons and swaps; that is how the insertion sort gains a speed advantage over the bubblesort.

#include <iostream>

int main() {
    using namespace std;

    int iaArray[] = {24, 5, 3, 35, 14, 23, 19};
    int iLength = 7;

    // Insertion sort
    for (int iIndex = 1; iIndex < iLength; ++iIndex) {
        // Initialize a local insertion index
        int iInsert = iIndex;
        while (iInsert > 0 && iaArray[iInsert - 1] > iaArray[iInsert]) {
            int iSwap             = iaArray[iInsert];
            iaArray[iInsert]      = iaArray[iInsert - 1];
            iaArray[iInsert - 1]  = iSwap;
            --iInsert;
        }
    }

	// Output the sorted array
    for (int iIndex = 0; iIndex < iLength; ++iIndex) {
        cout << iaArray[iIndex] << "  ";
    }
    cout << endl;

	cin.get();
    return 0;
}

The code for the insertion sort is very simple. Above, we show the C++ code of the insertion sort. The entire insertion sort is contained inside of the for-loop. The rest of the code is just initialization and outputting the elements afterward to show that they are sorted. The output of the program shown above looks like this: