Insertion sort is one of the standard algorithms you will come across studying Computer Science for GCSE and A Level. There are many different versions of the code for it scattered across the internet, but there are basically three common “flavours” you will find.

In this article we will look at some Python implementations. First of all, take a look at a visualisation of the algorithm, such as the one here.

The basic idea is this:

• You have a list to be sorted and two loops.

• An outer loop inches its way through the list from the second position, going one position further through on each iteration.

• On each of these iterations (or “passes”), the item at the current position is compared with its neighbour to the left. If it is smaller, then it swaps places, and this continues until our item is no longer smaller than its left-hand neighbour.

• Since in this algorithm the left-hand part of the list is always sorted (even when it’s just one item long!) we can stop at this point in the inner loop. We then increment the counter for the outer loop and do another pass, continuing like this until the list is sorted.

Now that may sound confusing, and it certainly can be until you have spent some time really thinking about it and trying it out for your self, preferably with something like some cards numbered from 1 – 10 or some playing cards.

Our first Python version looks like this:

l = [7, 2, 4, 3, 6, 5, 1]  # The list we wish to sort

for i in range(1, len(l)):  # Outer loop. l[1] is the second position.
    for j in range(i, 0, -1):  # Inner loop. -1 is the step value.
        if l[j] < l[j - 1]:  # Is our current item is too small?
            l[j], l[j - 1] = l[j - 1], l[j]  # Swap if needed.
        else:
            break

print(l)

An important thing about all variations of this algorithm is that the outer loop starts at the beginning and moves towards the end, but the inner loop starts from the position of the outer loop counter and moves towards the start of the list.

A more common version uses a while loop instead of the inner for loop:

l = [7, 2, 4, 3, 6, 5, 1]  # The list we wish to sort

for i in range(1, len(l)):
    j = i
    while (l[j] < l[j - 1]) and j > 0:
        l[j], l[j - 1] = l[j - 1], l[j]
        j -= 1

print(l)

Here, the inner loop is handled using while which as you probably know uses condition checking to determine whether to continue looping. The exit conditions are either getting the to start of the list (remember the inner loop goes backwards), or not needing to swap any more elements. (Remember the left-hand part of the list is always sorted).

Again, take some time to understand this version, using whatever aids you find useful (tracing variables, using cards, visualisations etc.)

Our final version is another improvement which replaces the “swapping” part of the algorithm with “shifting.” This version will again probably take some time to understand. One way to think of it is that your create a “hole” where the current item in the outer loop is, and then shift the larger values into the hole, repeating until the hole is in the correct place to insert the element.

There is a great video showing how this works here.

In Python, the code for this variation looks like this:

l = [7, 2, 4, 3, 6, 5, 1]

for i in range(1, len(l)):
    value = l[i]
    hole = i - 1
    while l[hole] > i and hole > -1:
        l[hole + 1] = l[hole]
        hole -= 1
    l[hole + 1] = i

print(l)

Finally, for anyone studying Cambridge International AS and A Level Computer Science (9608), the following is a Python implementation of insertion sort based on that syllabus. Note that it is logically equivalent to the above version.

listToBeSorted = [7, 2, 4, 3, 6, 5, 1]

for pointer in range(1, len(listToBeSorted)):
    itemToBeInserted = listToBeSorted[pointer]
    currentIndex = pointer - 1
    while listToBeSorted[currentIndex] > itemToBeInserted and currentIndex > -1:
        listToBeSorted[currentIndex + 1] = listToBeSorted[currentIndex]
        currentIndex -= 1
    listToBeSorted[currentIndex + 1] = itemToBeInserted

print(listToBeSorted)

So there you have insertion sort – one of the standard algorithm required for GCSE and/or A Level Computer Science. Make sure you fully understand it, even if it takes some work to get there. Then test yourself by coding it yourselves without looking at existing code.

Good luck, and enjoy.

Sharing is caring!