Insertion Sort

Insertion sort builds a sorted prefix one element at a time. Each new element is inserted into the correct place inside the already sorted part.

It is easy to visualize and useful for understanding how a loop can maintain a sorted region.

Core Idea

At the start of each outer loop iteration, the left side of the array is already sorted. The algorithm takes the next value and shifts larger values right until the correct position is open.

The worst-case time complexity is O(n^2). The extra space is O(1) for an in-place implementation.

The loop invariant is that values[:i] is sorted before inserting values[i]. The algorithm preserves that invariant by placing the current value into the correct position inside the sorted prefix.

Function Contract

insertion_sort(values) expects a mutable list whose elements can be compared with >.

It sorts the list in place and returns None. The caller observes the result by reading the same list after the function finishes.

Python Example

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

After each outer loop, values[:i + 1] is sorted.

Step-by-Step Example

Start with:

[5, 2, 4, 1]

The sorted prefix begins as [5]. Insert 2 by shifting 5 right, producing [2, 5, 4, 1]. Then insert 4 into [2, 5], producing [2, 4, 5, 1]. Finally insert 1, producing [1, 2, 4, 5].

At no point does the algorithm sort the whole list from scratch. It grows a sorted prefix.

Why It Works

Before inserting the current value, the prefix to the left is already sorted. Shifting larger values one position right creates the exact gap where the current value belongs. Values smaller than or equal to the current value stay on the left, and larger shifted values end up on the right.

After insertion, the prefix is one element longer and still sorted.

Complexity

The best case is O(n) when the list is already sorted, because the inner loop barely moves. The worst case is O(n^2) when many elements must shift. Extra space is O(1).

Common Confusions

Insertion sort is not the usual way to sort in Python. Python’s built-in sort is much more capable.

The algorithm is still worth learning because it makes loop invariants and nearly sorted input behavior easy to see.

Another common mistake is overwriting the current value before saving it. The variable current protects the value while larger elements shift right.

When To Use It

Use insertion sort as a learning tool, for very small inputs, or when reasoning about algorithms that grow a sorted region incrementally.

Do not use it for large unsorted inputs when a general O(n log n) sorting method is available.

The Main Point

Insertion sort grows a sorted prefix. It is not a production sorting tool for large inputs, but it is a clear example of maintaining a loop invariant.