Insertion Sort

Phase 1f(x)

The Mathematics

Loop invariant, stability, and case analysis

Loop Invariant

At the start of each outer loop iteration $i$ , the subarray $A[0..i-1]$ consists of the elements originally in $A[0..i-1]$ but in sorted order:

\text{Invariant: } A[0] \leq A[1] \leq \cdots \leq A[i-1]

Each iteration takes element $A[i]$ (the key) and inserts it into the correct position within the sorted prefix, extending the sorted region by one.

Complexity Analysis

The number of comparisons depends on the input order:

\text{Best case (sorted): } T(n) = O(n)

Each key is already in place — inner loop never executes.

\text{Worst case (reverse sorted): } T(n) = O(n^2)

Each key shifts all the way to position 0: $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$ .

\text{Average case: } T(n) = O(n^2)

Expected comparisons: $\sum_{i=1}^{n-1} \frac{i}{2} = \frac{n(n-1)}{4}$ .

Properties

Insertion sort has several useful properties:

$\bullet$ Stable: equal elements maintain their relative order (compare with $>$ , not $\geq$ )

$\bullet$ In-place: uses only $O(1)$ extra space

$\bullet$ Adaptive: runs in $O(n + d)$ where $d$ is the number of inversions

$\bullet$ Online: can sort elements as they arrive

When to Use Insertion Sort

Optimal for small arrays ( $n \leq 20$ ) or nearly-sorted data. Many hybrid algorithms (Timsort, introsort) use insertion sort as a subroutine for small partitions.

Phase 2▶

See It Work

Sorting [5, 2, 8, 1, 9, 3] by inserting each element into the sorted prefix

Sorted Key Comparing

\text{Invariant: } A[0..0] \text{ is sorted}

Step 1 of 11

Initialize: first element [5] is trivially sorted. Start from index 1.

Phase 3</>

The Code

Bridge from loop invariant to Python implementation

Mathematical Formulation

i = 1, 2, \ldots, n-1

Outer loop extends the sorted region one element at a time

\text{key} = A[i]

Save the current element to insert into the sorted prefix

j \geq 0 \;\land\; A[j] > \text{key}

Inner loop finds where key belongs by scanning right to left

A[j+1] \leftarrow A[j]

Shift larger elements one position to the right

A[j+1] \leftarrow \text{key}

Place the key at its correct sorted position

\text{Invariant: } A[0..i] \text{ sorted after iteration } i

Loop invariant: after each outer iteration, A[0..i] is sorted

Python Implementation

def insertion_sort(A):
    n = len(A)
    for i in range(1, n):             # Outer: extend sorted region
        key = A[i]                    # Element to insert
        j = i - 1
        while j >= 0 and A[j] > key: # Inner: find insertion point
            A[j + 1] = A[j]          # Shift element right
        A[j + 1] = key               # Insert key at correct position
    return A