Insertion Sort

Insertion sort builds a sorted prefix one element at a time, shifting each new element back to its correct position. It is fast on small or nearly-sorted inputs and is the inner sort used by Timsort, Introsort, and many hybrid algorithms.

Complexity

Best	Average	Worst	Space (Worst)
`Ω(n)`	`Θ(n²)`	`O(n²)`	`O(1)`

How it works

For i from 1 to n−1: take element arr[i] and slide it leftward, swapping with each larger element on its left, until it finds its slot. The first i elements stay sorted as an invariant. On nearly-sorted data each element shifts only a constant number of times — that's the O(n) best case.

Python implementation

def insertion_sort(arr):
    """In-place insertion sort."""
    for i in range(1, len(arr)):
        x = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > x:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = x
    return arr


print(insertion_sort([3, 6, 1, 8, 2, 9, 4]))  # [1, 2, 3, 4, 6, 8, 9]

Trade-offs

Stable, in-place, O(1) extra memory.
O(n) on already-sorted or nearly-sorted input — adaptive.
O(n²) on random or reverse-sorted input.
The go-to sort for tiny subarrays inside hybrid sorts (Timsort cuts over to it for runs < 32).

← Back to Algorithms