Insertion Sort

Sorting a Hand of Playing Cards

Unlike Selection Sort (which scans the entire unsorted suffix to pick the global minimum), Insertion Sort takes whatever element happens to sit next at key = a[i] and inserts it into the already-sorted prefix a[0 .. i - 1]:

1. Save key = a[i] in a register.
2. Walk j leftward from i - 1 down to 0 while a[j] > key, shifting a[j + 1] = a[j] one slot to the right.
3. The moment j < 0 or a[j] <= key, stop immediately and write a[j + 1] = key.

Because the inner while loop stops on the first a[j] <= key, two crucial properties fall out for free:

• Stability: Equal elements never cross each other.
• Linear O(n + I) adaptivity: Every inner shift eliminates exactly one inversion (j < i with a[j] > a[i]). If an array has only k out-of-place pairs, Insertion Sort finishes in O(n + k) time!

Iterative vs. Recursive Insertion Sort

As explored in our companion @bigocast episode (Recursive Insertion Sort), Insertion Sort also has a clean inductive definition: recursively sort the first n - 1 items, then insert a[n - 1] into that sorted prefix.

def insertion_sort(nums: list[int]) -> list[int]:
    """Iterative in-place Insertion Sort: O(n + inversions) time, O(1) space."""
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums


def insertion_sort_recursive(nums: list[int], n: int | None = None) -> list[int]:
    """Recursive formulation: O(n) call-stack depth (pedagogical view of induction)."""
    if n is None:
        n = len(nums)
    if n <= 1:
        return nums

    insertion_sort_recursive(nums, n - 1)

    key = nums[n - 1]
    j = n - 2
    while j >= 0 and nums[j] > key:
        nums[j + 1] = nums[j]
        j -= 1
    nums[j + 1] = key
    return nums

Why Production Standard Libraries Still Use Insertion Sort

Divide-and-conquer sorts like Merge Sort and Quicksort pay function-call and branching overhead on tiny slices. When subproblem size drops to 16–32 elements, a[0 .. 31] fits inside two CPU cache lines (128 bytes), so production hybrids (Timsort in Python/Java and Introsort in C++) switch to Insertion Sort at the leaves!