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.

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.

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.

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.