Insertion Sort

Algorithm

Insertion Sort is an incremental algorithm: it builds a sorted prefix one element at a time. For each element $A[j]$, find its correct position within the already-sorted prefix $A[1 \dots j-1]$, shift larger elements right, and insert.

Steps (1-indexed pseudocode convention):

1. For $j = 2$ to $A.\text{length}$:
2.  $\text{Key} = A[j]$
3.  $i = j - 1$
4.  While $i > 0$ and $A[i] > \text{Key}$:
5.   $A[i+1] = A[i]$
6.   $i = i - 1$
7.  $A[i+1] = \text{Key}$

Visual Description

The algorithm maintains two regions: $A[1 \dots j-1]$ is sorted, $A[j \dots n]$ is yet to be processed. At each step, peel off $A[j]$, walk backwards through the sorted region shifting any larger element right by one position, then drop the key into the gap.

Correctness

Loop invariant: At the start of each FOR iteration, $A[1 \dots j-1]$ consists of the original first $j-1$ elements in sorted order.

• Initialisation ($j=2$): $A[1]$ is a single element, trivially sorted.
• Maintenance: The WHILE loop shifts all elements greater than Key right by one, preserving sortedness; inserting Key at the correct position extends the sorted prefix by one.
• Termination ($j=n+1$): The entire array $A[1 \dots n]$ is sorted.

Complexity Analysis

The running time depends on $t_j$, the number of WHILE-loop iterations for each $j$:

$T(n) = a \cdot n + b \cdot (n-1) + d\sum_{j=2}^{n} t_j + e\sum_{j=2}^{n} (t_j - 1)$

Best Case: $\Theta(n)$

Input already sorted. $t_j = 1$ for all $j$ (only the failing comparison, no shifts). $T(n) = pn + q$.

Worst Case: $\Theta(n^2)$

Input reverse-sorted. $t_j = j$ (shift all previous elements). The comparison count alone is:

$\sum_{j=2}^{n} (j-1) = \frac{n(n-1)}{2} = \Theta(n^2)$

Average Case: $\Theta(n^2)$

On a random permutation, each element moves past roughly half the sorted prefix. The quadratic term carries a factor of $1/2$ but remains $\Theta(n^2)$.

Properties

Property	Value
In-place	Yes, $O(1)$ extra space
Stable	Yes, equal keys stay in original relative order
Adaptive	Efficient on nearly-sorted data (approaches $O(n)$)
Online	Can sort items as they arrive

When to Use

Insertion Sort outperforms $\Theta(n \log n)$ algorithms for small $n$ (roughly $n < 50$) due to low constant factors and excellent cache locality. It is also ideal for nearly-sorted data or as the base case inside recursive sorts (e.g. switching to Insertion Sort when subarrays fall below a threshold).

Summary

Aspect	Detail
Strategy	Incremental, build sorted prefix
Invariant	$A[1 \dots j-1]$ is sorted
Best case	$\Theta(n)$, already sorted
Worst case	$\Theta(n^2)$, reverse-sorted
Average case	$\Theta(n^2)$
Comparisons worst	$n(n-1)/2$
In-place	Yes
Stable	Yes