An insertion sort builds a sorted list one item at a time, much like sorting playing cards in your hand. The list is treated as a sorted part on the left and an unsorted part on the right.

At the start only the first item counts as sorted. Each pass takes the next unsorted item and inserts it into its correct place in the sorted part, so the sorted part grows by one item every pass.

In each pass the item being inserted is copied into a variable, usually called the key.

1. Compare the key with the item to its left.
2. If that item is larger, shift it one place to the right.
3. Repeat until a smaller or equal item is found, or the start of the list is reached.
4. Place the key in the gap.

A list of n items always needs n − 1 passes.

To hand-trace an insertion sort, write out the list after every pass. The bar shows where the sorted part ends, and the key for each pass is in brackets.

Start        6 | 3  8  2  5
Pass 1 (3)   3  6 | 8  2  5     6 shifted right
Pass 2 (8)   3  6  8 | 2  5     no shift needed
Pass 3 (2)   2  3  6  8 | 5     8, 6 and 3 shifted
Pass 4 (5)   2  3  5  6  8      8 and 6 shifted

Pass 2 shows why the algorithm is quick on nearly sorted data: an item already in place needs only one comparison.

This in-place version sorts the original list without making a new one. The outer loop picks each key in turn; the inner while loop shifts larger items right until the gap is in the correct position.

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

scores = [6, 3, 8, 2, 5]
insertion_sort(scores)
print(scores)

[2, 3, 5, 6, 8]

Using > rather than >= in the while loop means equal items are never moved past each other, which keeps the sort stable.

Benefits

• Simple to understand and to code.
• In place: only a few extra variables are needed, whatever the list size.
• Stable: equal items keep their original order.
• Fast on small or nearly sorted lists, with a best case of O(n).

Drawbacks

• Average and worst cases are O(n²), so it is slow on large lists.
• A list in reverse order is the worst case, because every key shifts all the way to the front.

Adding one print statement to the outer loop turns the function into a tracer that shows the list after every pass, just like a hand trace.

def insertion_sort_trace(items):
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:
            items[j + 1] = items[j]
            j = j - 1
        items[j + 1] = key
        print("Pass", i, items)

insertion_sort_trace(["Mia", "Ali", "Zoe", "Ben"])

Pass 1 ['Ali', 'Mia', 'Zoe', 'Ben']
Pass 2 ['Ali', 'Mia', 'Zoe', 'Ben']
Pass 3 ['Ali', 'Ben', 'Mia', 'Zoe']

The same code sorts strings, such as names in a class register, because Python compares them alphabetically. Changing items[j] > key to items[j] < key sorts into descending order instead.

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works by taking elements from the unsorted part and inserting them into their correct position in the sorted part.

The process is similar to sorting playing cards in your hands: you pick cards one by one and insert each card into the correct position relative to the cards already held.

Step-by-step explanation:

• Start with the second element, assuming the first element is sorted.
• Compare the current element with those before it.
• Shift all larger elements one position to the right.
• Insert the current element into its correct position.
• Repeat for all elements.

Below is a simple Python implementation of insertion sort:

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

This algorithm is useful for small datasets or datasets that are already mostly sorted because it is efficient in those cases. However, it is not suitable for large datasets due to its O(n²) average and worst-case complexity.

Practical applications include:

• Sorting small lists in embedded systems.
• Useful as part of more complex algorithms like Timsort.
• Online sorting where data arrives sequentially.