Insertion Sort

The sorted-prefix invariant

At the start of pass i, the prefix a[0:i] contains exactly the first i input records in stable sorted order. It is sorted, but its values are not necessarily in their final global positions; a later smaller key may shift the whole prefix right.

Interactive: key, gap, and sorted prefix

The key register makes the saved value explicit. Each shift performs one array write and moves the gap left; the final insertion performs one more write. Compare nearly sorted and reverse inputs to see adaptivity in the counters.

Reference implementation

Save the key before shifting. Otherwise the first write overwrites it. Shifts are preferable to repeated adjacent swaps because one displaced value costs one array write instead of two.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1

        # Shift only strictly larger values: this preserves stability.
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1

        a[j + 1] = key

    return a

final class InsertionSort {
    static int[] sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;

            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }

            a[j + 1] = key;
        }

        return a;
    }
}

Pass-by-pass trace

The bar marks the sorted-prefix boundary for [5, 2, 4, 6, 1, 3]. Every row inserts the first value to the right of the bar, then moves the boundary one position right.

Inversions explain the running time

An inversion is a pair i < j with a[i] > a[j]. When key a[i] is inserted, the algorithm shifts once for each earlier value that forms an inversion with it. Across the whole run, the number of shifts is therefore exactly the original inversion count I.

Why it works well on small or nearly sorted ranges

Binary insertion: fewer comparisons, same movement

Because the prefix is sorted, binary search can find the insertion position in Θ(log i) comparisons. But an array must still shift up to i values, so worst-case time remains Θ(n²). This variant matters when comparisons are expensive: long strings or computed keys, but writes are comparatively cheap.

def binary_insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]

        # upper_bound: insert after existing equal keys for stability
        lo, hi = 0, i
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] <= key:
                lo = mid + 1
            else:
                hi = mid

        a[lo + 1:i + 1] = a[lo:i]  # conceptual right shift
        a[lo] = key

final class BinaryInsertionSort {
    static void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];

            // upper_bound: insert after equals for stability
            int lo = 0;
            int hi = i;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (a[mid] <= key) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }

            for (int j = i; j > lo; j--) {
                a[j] = a[j - 1];
            }
            a[lo] = key;
        }
    }
}

The slice assignment is concise Python, not an in-place O(1)-space teaching implementation: Python materializes a temporary slice. Use an explicit backward shift when auxiliary-space accounting matters.

Shifts versus adjacent swaps

Variants and data-structure nuances

Edge cases and reasoning