# 6.3 Insertion Sort

# 6.3 Insertion Sort

Insertion sort builds a sorted prefix one element at a time. At step `i`, the prefix `A[0..i-1]` is already sorted, and the algorithm inserts `A[i]` into its correct position inside that prefix. This is the same operation used when sorting cards by hand: keep the left side ordered, take the next card, and slide it left until it belongs.

## Problem

You have an array `A[0..n-1]`. You want to sort it in place, preserve stability, and perform well when the input is already sorted or nearly sorted.

## Solution

Store the next element in a temporary variable, shift larger elements one position to the right, and write the stored element into the gap.

```text
insertion_sort(A):
  n = length(A)

  for i = 1 to n - 1:
    key = A[i]
    j = i - 1

    while j >= 0 and A[j] > key:
      A[j + 1] = A[j]
      j = j - 1

    A[j + 1] = key
```

The comparison uses `A[j] > key`, not `A[j] >= key`. This detail gives the standard algorithm its stability. Equal elements are not shifted past the new element, so their relative order is preserved.

## Example

Start with:

```text
[5, 2, 4, 1, 3]
```

At `i = 1`, the key is `2`. The element `5` is larger, so it shifts right:

```text
[5, 5, 4, 1, 3]
```

Then `2` is written into the gap:

```text
[2, 5, 4, 1, 3]
```

At `i = 2`, the key is `4`. The element `5` shifts right, and `4` is placed after `2`:

```text
[2, 4, 5, 1, 3]
```

At `i = 3`, the key is `1`. The elements `5`, `4`, and `2` shift right:

```text
[2, 2, 4, 5, 3]
```

Then `1` fills the first position:

```text
[1, 2, 4, 5, 3]
```

At `i = 4`, the key is `3`. The elements `5` and `4` shift right, and `3` is inserted after `2`:

```text
[1, 2, 3, 4, 5]
```

## Invariant

At the start of each outer-loop iteration with index `i`, the prefix `A[0..i-1]` is sorted and contains exactly the first `i` elements from the original array, possibly in a different order.

Initially, when `i = 1`, the prefix `A[0..0]` has one element, so it is sorted. During the iteration, the algorithm removes `A[i]` into `key`, shifts all larger elements in the prefix one position to the right, and then writes `key` into the unique position where the left neighbor is less than or equal to it and the right neighbor is greater than it.

The shifting step preserves the multiset of elements because it only copies existing prefix elements into adjacent positions while `key` is stored separately. Once `key` is written into the gap, the prefix `A[0..i]` contains exactly the first `i + 1` original elements and is sorted.

When the loop terminates, `i = n`, so the whole array is a sorted permutation of the input.

## Correctness

Insertion sort satisfies the permutation condition because every iteration only moves elements inside the array and restores the saved `key`. No element is created or discarded.

It satisfies the order condition because the insertion step places `key` after every prefix element less than or equal to it and before every prefix element greater than it. Elements that are shifted right were already in sorted order, so their internal order is preserved. Elements that remain on the left were also already in sorted order. Therefore the enlarged prefix is sorted.

This proof depends on the fact that the prefix was sorted before insertion. Insertion sort never tries to repair arbitrary disorder across the whole array at once. It repairs exactly one boundary: the boundary between the sorted prefix and the next unsorted element.

## Complexity

In the worst case, the input is reverse sorted. Each new element must move all the way to the front. The number of comparisons and shifts is quadratic:

```text
1 + 2 + ... + (n - 1) = n(n - 1) / 2
```

So the worst-case running time is:

```text
O(n^2)
```

The extra memory usage is:

```text
O(1)
```

In the best case, the input is already sorted. The inner loop fails immediately on each iteration, so the algorithm performs one comparison per outer iteration and no shifts:

```text
O(n)
```

This adaptiveness is the main practical advantage of insertion sort.

## Stability

Insertion sort is stable when the inner loop shifts only elements strictly greater than `key`.

Consider:

```text
[(2, A), (1, B), (2, C)]
```

After sorting by the numeric key, the stable result is:

```text
[(1, B), (2, A), (2, C)]
```

The records `(2, A)` and `(2, C)` remain in the same relative order. This happens because when `key = (2, C)`, the earlier equal key `(2, A)` is not shifted past it.

If the loop used `A[j] >= key`, the algorithm would move equal elements to the right and stability would be lost.

## Implementation Notes

Insertion sort is useful for small arrays, nearly sorted arrays, and as a base case inside hybrid algorithms. Many production sorting algorithms switch to insertion sort for small partitions because its overhead is low and its memory access pattern is simple.

A common hybrid pattern is:

```text
hybrid_sort(A, lo, hi):
  if hi - lo <= threshold:
    insertion_sort_range(A, lo, hi)
  else:
    divide_and_conquer_sort(A, lo, hi)
```

The threshold is implementation dependent. It is usually chosen by benchmarking rather than by asymptotic analysis.

## Common Bugs

The most common bug is losing `key` before shifting. Always store `A[i]` before overwriting positions.

Another common bug is writing `key` to `A[j]` instead of `A[j + 1]`. The loop stops after decrementing `j` past the insertion location, so the gap is at `j + 1`.

A third bug is using an unsigned index for `j` in languages where `j >= 0` is always true. In C, C++, or Rust-style code, handle the boundary carefully or rewrite the loop to avoid underflow.