Python Insertion Sort

Insertion sort is a simple, comparison-based sorting algorithm that builds a sorted portion of a list one element at a time, the same way most people sort a hand of playing cards. It repeatedly takes the next unsorted element and inserts it into its correct position among the already-sorted elements. Although its worst-case performance is O(n²), insertion sort is fast for small or nearly-sorted lists, uses almost no extra memory, and is a building block inside real-world sorting algorithms like Python’s own Timsort. Learning it thoroughly also teaches core ideas — in-place mutation, loop invariants, and stability — that apply to every other sorting algorithm you’ll encounter.

Overview: How Insertion Sort Works

Insertion sort divides a list into two conceptual regions: a sorted region at the front and an unsorted region at the back. Initially the sorted region contains just the first element (a single element is trivially “sorted”), and the unsorted region contains everything else. The algorithm then repeats one step: take the first element of the unsorted region (called the key), and shift it leftward past every element in the sorted region that is greater than it, until it lands in its correct spot. After each step, the sorted region grows by one element, and eventually the whole list is sorted.

Internally, Python lists store references to objects, not the objects themselves. When insertion sort does arr[j + 1] = arr[j], it is copying a reference — not duplicating the underlying object — so the operation is cheap regardless of how large the elements are. The comparison arr[j] > key calls the element’s __gt__ method under the hood, which is why insertion sort (like all of Python’s built-in sorting) works on any type that defines ordering: numbers, strings, tuples, or custom classes that implement rich comparison methods.

Insertion sort is:

• In-place — it rearranges the original list using O(1) extra space (aside from the loop variables).
• Stable — equal elements keep their original relative order, provided you use a strict > comparison (see the Common Mistakes section).
• Adaptive — the closer the input is to already sorted, the faster it runs. A fully sorted list takes only O(n) time because the inner while loop never executes.
• Online — it can sort a stream of data as it arrives, inserting each new element into the already-sorted portion without needing to see the rest of the data first.

Its time complexity is O(n) in the best case (already sorted), O(n²) in the average and worst cases (reverse sorted), and its space complexity is O(1). Because of the O(n²) behavior on large random inputs, insertion sort is rarely used to sort big datasets on its own — but CPython’s built-in sort() and sorted() (which use Timsort) automatically switch to an insertion sort for small runs of about 64 elements or fewer, because the low constant-factor overhead makes it faster than more complex algorithms at that scale.

Syntax

Insertion sort is not a built-in Python keyword or function — you write it yourself as a function. The canonical form looks like this:

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

Part	Meaning
arr	The list being sorted in place.
i	Index of the next unsorted element to insert; starts at 1 since a single element is already “sorted”.
key	The value currently being inserted into the sorted region.
j	Index that scans backward through the sorted region looking for key‘s correct position.
j >= 0 and arr[j] > key	Loop condition — checks the bound first so Python’s short-circuit evaluation never indexes arr[j] once j is negative.
arr[j + 1] = arr[j]	Shifts a larger element one slot to the right to make room.
arr[j + 1] = key	Drops key into the gap once the correct position is found.

Examples

Example 1: Sorting a List of Numbers

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

numbers = [9, 5, 1, 4, 3]
print("Before:", numbers)
insertion_sort(numbers)
print("After:", numbers)

Output:

Before: [9, 5, 1, 4, 3]
After: [1, 3, 4, 5, 9]

This is the textbook version. Notice the function sorts numbers in place — the same list object is mutated — and also returns it, so you could chain calls like sorted_list = insertion_sort(numbers) if you prefer. Each pass through the outer loop grows the sorted prefix by exactly one element.

Example 2: Sorting by a Custom Key

def insertion_sort_by_key(arr, key=lambda x: x, reverse=False):
    for i in range(1, len(arr)):
        current = arr[i]
        current_key = key(current)
        j = i - 1
        while j >= 0:
            should_shift = key(arr[j]) < current_key if reverse else key(arr[j]) > current_key
            if not should_shift:
                break
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = current
    return arr

words = ["banana", "kiwi", "apple", "fig", "cherry"]
insertion_sort_by_key(words, key=len)
print(words)

Output:

['fig', 'kiwi', 'apple', 'banana', 'cherry']

Real-world sorting rarely compares raw values directly — you usually sort by some derived property. This version mirrors the key argument used by Python’s built-in sorted(), computing key(current) once per element and comparing that instead of the element itself. Here it sorts strings by length. Notice "banana" and "cherry" are both length 6 and keep their original relative order — that’s stability in action.

Example 3: Binary Insertion Sort

import bisect

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        pos = bisect.bisect_left(arr, key, 0, i)
        arr = arr[:pos] + [key] + arr[pos:i] + arr[i + 1:]
    return arr

data = [8, 3, 7, 4, 2]
result = binary_insertion_sort(data)
print(result)

Output:

[2, 3, 4, 7, 8]

The classic algorithm uses a linear scan to find where key belongs, which takes O(n) comparisons per element. Since the sorted region is already sorted, you can find the insertion point faster with a binary search using the standard library’s bisect module — that reduces the number of comparisons to O(log n) per element. The total time complexity is still O(n²) overall, though, because inserting into a Python list (or shifting elements) is still an O(n) operation regardless of how quickly you locate the position. This variant is mainly useful when comparisons are expensive (for example, comparing large strings or calling a slow custom __lt__).

Under the Hood: Step-by-Step Trace

Let’s trace insertion_sort([9, 5, 1, 4, 3]) from Example 1 one pass at a time to see exactly what the interpreter does:

i	key	Shifts performed	List state after pass
1	5	9 shifts right past 5	[5, 9, 1, 4, 3]
2	1	9 and 5 shift right past 1	[1, 5, 9, 4, 3]
3	4	9 and 5 shift right past 4 (1 stays)	[1, 4, 5, 9, 3]
4	3	9, 5 and 4 shift right past 3 (1 stays)	[1, 3, 4, 5, 9]

At the start of every pass, everything to the left of index i is guaranteed to already be sorted — that guarantee is called the loop invariant, and it’s what lets you reason about correctness: if the invariant holds before the pass and the pass preserves it, then by induction the whole list ends up sorted once i reaches the end. Each inner while iteration does exactly one comparison and, if needed, one assignment — no swapping of two variables is required (unlike bubble sort), because key already holds a safe copy of the value being inserted.

Common Mistakes

Mistake 1: Forgetting the Bounds Check

It’s easy to write the inner loop’s condition without protecting against j going negative:

def buggy_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while arr[j] > key:  # missing "j >= 0"!
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

try:
    buggy_insertion_sort([1, 0])
except IndexError as e:
    print(f"Crashed: {e}")

Output:

Crashed: list index out of range

Without the j >= 0 check, once j becomes -1, Python happily evaluates arr[-1] (Python allows negative indexing, so this doesn’t fail immediately) and the comparison may keep passing, decrementing j further into -2, -3, and so on until it steps outside the valid negative index range and raises IndexError. The fix is to always put the bound check first, joined with and, so short-circuit evaluation stops the loop before arr[j] is ever evaluated with an invalid index: while j >= 0 and arr[j] > key:.

Mistake 2: Using >= Instead of > and Losing Stability

def unstable_insertion_sort(arr, key=lambda x: x):
    for i in range(1, len(arr)):
        current = arr[i]
        current_key = key(current)
        j = i - 1
        while j >= 0 and key(arr[j]) >= current_key:  # bug: >= breaks stability
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = current
    return arr

tasks = [("email", 2), ("backup", 1), ("cleanup", 2), ("report", 1)]
unstable_insertion_sort(tasks, key=lambda t: t[1])
print(tasks)

Output:

[('report', 1), ('backup', 1), ('cleanup', 2), ('email', 2)]

The sort is still numerically correct — priorities 1 come before 2 — but "report" now appears before "backup", even though "backup" came first in the original list. Using >= makes the algorithm shift equal elements past each other, silently reordering them. If downstream code relies on ties keeping their original order (a very common assumption, e.g. “sort by priority, but keep submission order for ties”), this is a real bug. The fix is to use a strict > comparison:

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

tasks = [("email", 2), ("backup", 1), ("cleanup", 2), ("report", 1)]
stable_insertion_sort(tasks, key=lambda t: t[1])
print(tasks)

Output:

[('backup', 1), ('report', 1), ('email', 2), ('cleanup', 2)]

Now both priority-1 tasks and both priority-2 tasks keep their original relative order.

Best Practices

• For real code, use Python’s built-in sorted() or list.sort() — both use Timsort, which is stable, highly optimized in C, and adapts to partially-sorted data. Write insertion sort yourself only for learning, interviews, or genuinely tiny/streaming datasets.
• Keep the bound check (j >= 0) as the first operand of the and in the inner loop condition so short-circuit evaluation protects the index access.
• Use a strict > (not >=) comparison if you need a stable sort, which is the expected default behavior in almost all practical use cases.
• Prefer a key function over a custom comparator — computing key(x) once per element and comparing keys is clearer and faster than repeatedly re-deriving the comparison value.
• Don’t reach for insertion sort on large, randomly-ordered datasets; its O(n²) behavior gets expensive quickly past a few thousand elements. It shines specifically on small lists (roughly under 50 elements) or lists that are already almost sorted.
• If you need to sort as data streams in one item at a time and want the list sorted at every step, insertion sort (or the bisect.insort function, which does the same thing using binary search) is a genuinely good fit.
• Add type hints (e.g. def insertion_sort(arr: list[int]) -> list[int]:) so callers and IDEs know what the function expects and returns.

Practice Exercises

1. Write a function insertion_sort_descending(arr) that sorts a list of numbers in descending order, without calling reverse() or sorted(..., reverse=True). Test it on [3, 7, 1, 9, 2] and confirm you get [9, 7, 3, 2, 1].
2. Modify the standard insertion_sort function to also count and return the number of shift operations it performs (each execution of arr[j + 1] = arr[j] counts as one shift). Run it on an already-sorted list like [1, 2, 3, 4, 5] and on a reverse-sorted list like [5, 4, 3, 2, 1] — how many shifts does each take, and why does this confirm insertion sort’s best-case and worst-case behavior?
3. Using bisect.insort from the standard library, write a function that takes a list of numbers one at a time (simulate this with a for loop over a source list) and inserts each into a running sorted list, printing the sorted list after each insertion. This mimics how insertion sort can process a live stream of data.

Summary

• Insertion sort builds a sorted region one element at a time by inserting each new element into its correct position among the already-sorted elements.
• It is in-place (O(1) extra space), stable when using strict > comparisons, adaptive (O(n) on already-sorted input), and works online on streaming data.
• Its overall time complexity is O(n) best case and O(n²) average/worst case, which makes it a poor choice for large random datasets but excellent for small or nearly-sorted ones.
• Python’s own Timsort (used by sorted() and list.sort()) uses insertion sort internally for small runs — it’s not just a textbook exercise.
• Always check j >= 0 before indexing arr[j], and put it first in the and so short-circuit evaluation protects you.
• Use > rather than >= in the shift condition to preserve stability.
• For real production code, prefer the built-in sorted()/list.sort(), or bisect.insort for maintaining a sorted list incrementally.