Knowledge organisersSearching and sorting algorithms

Standard sorting algorithms: Insertion sort

Knowledge organiser

Searching and sorting algorithms

2.1.3e

Understand the main steps of each algorithm, Understand any pre-requisites of an algorithm, Apply the algorithm to a data set, Identify an algorithm if given the code or pseudocode for it

What you need to know

Insertion sort works by building a sorted section of the list one item at a time. Starting from the second item, each element is compared to those already sorted and inserted into its correct position. It is simple to understand and efficient for small to medium-sized lists, but slower than merge sort for very large datasets.

Key points

The array has two sections: a SORTED section (left) and an UNSORTED section (right). The sorted section builds from the START.
Start at the second item (index 1) since a single item is already 'sorted'.
Compare the current item to items on its left and insert it into the correct position.
A TEMP variable is used to store the value being moved, so it is not lost/overwritten during the swap process.
The OUTER loop is count-controlled (for loop) — it visits each item once.
The INNER loop is condition-controlled (while loop) — because we don't know how many swaps/moves are needed to place the item correctly.
Exam Tip:Explain WHY the inner loop is condition-controlled: we do not know at run-time how many swaps/positions the item needs to move. It repeats WHILE the current item is smaller than the one to its left.
Key Point:The condition-controlled loop is more EFFICIENT than a count-controlled loop — it stops as soon as the correct position is found, rather than iterating unnecessarily.
Completes sorting in a SINGLE PASS through the array (the outer loop).
Efficient for small or nearly-sorted lists. Generally more efficient than bubble sort on average.
Less efficient than merge sort for large, unsorted datasets.

Code examples

Insertion sort in Python

python

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

print(insertion_sort([5, 3, 9, 4, 7]))
# Output: [3, 4, 5, 7, 9]

def insertion_sort(data): for i in range(1, len(data)): key = data[i] j = i - 1 while j >= 0 and data[j] > key: data[j + 1] = data[j] j -= 1 data[j + 1] = key return data print(insertion_sort([5, 3, 9, 4, 7])) # Output: [3, 4, 5, 7, 9]