# Insertion Sort

# Insertion Sort

Insertion sort builds the sorted array one element at a time. At each step, it takes the next element and inserts it into the correct position within the already sorted prefix.

It mirrors the process of sorting cards in hand. Compared to swap-based methods, it reduces writes by shifting elements.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

## Algorithm

Maintain a sorted prefix $A[0..i-1]$. Insert $A[i]$ into its correct position by shifting larger elements to the right.

```id="f3k8p2"
insertion_sort(A):
    n = length(A)
    for i from 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
```

## Example

Let

$$
A = [5, 2, 4, 6, 1, 3]
$$

Step 1:

Insert 2 into [5]

→ [2,5,4,6,1,3]

Step 2:

Insert 4 into [2,5]

→ [2,4,5,6,1,3]

Step 3:

Insert 6 into [2,4,5]

→ [2,4,5,6,1,3]

Step 4:

Insert 1 into [2,4,5,6]

→ [1,2,4,5,6,3]

Final result:

$$
[1,2,3,4,5,6]
$$

## Correctness

At iteration $i$, the prefix $A[0..i-1]$ is sorted. The algorithm inserts $A[i]$ into the correct position within this prefix by shifting all larger elements. This preserves sorted order and extends the sorted prefix by one element.

## Complexity

| case                  | comparisons             | time     |
| --------------------- | ----------------------- | -------- |
| best (already sorted) | $n$                     | $O(n)$   |
| worst                 | $\frac{n(n-1)}{2}$      | $O(n^2)$ |
| average               | $\approx \frac{n^2}{2}$ | $O(n^2)$ |

Space complexity:

$$
O(1)
$$

## Properties

* stable
* in-place
* adaptive to nearly sorted input
* efficient for small arrays

## When to Use

Insertion sort performs well when the input is small or nearly sorted. It is commonly used as a base case inside more advanced algorithms such as quicksort or mergesort.

## Implementation

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

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

        a[j + 1] = key

    return a
```

```id="z2m8q5"
func InsertionSort[T constraints.Ordered](a []T) {
    for i := 1; i < len(a); i++ {
        key := a[i]
        j := i - 1

        for j >= 0 && a[j] > key {
            a[j+1] = a[j]
            j--
        }

        a[j+1] = key
    }
}
```