Insertion sort

Insertion sort builds a sorted output one element at a time. Take the next unsorted element, walk back through the already-sorted prefix, and slide it leftward until it’s in the right place. After $n - 1$ insertions, the whole array is sorted.

The mental model: sorting a hand of playing cards. Pick up cards one at a time, slip each new card into its correct position among the cards already in your hand.

Algorithm

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];   // shift element right
            j--;
        }
        arr[j + 1] = key;          // place key in correct slot
    }
}

For each element starting at index 1:

Save the element as key.
Slide elements to its left rightward as long as they’re greater than key.
Insert key at the gap created.

Worked example

arr = [5, 2, 4, 6, 1, 3]:

i=1: key=2. Sorted prefix [5]. Slide 5 right; place 2. [2, 5, 4, 6, 1, 3].
i=2: key=4. Slide 5 right; place 4. [2, 4, 5, 6, 1, 3].
i=3: key=6. 6 ≥ 5, no shift. [2, 4, 5, 6, 1, 3].
i=4: key=1. Slide 6, 5, 4, 2 all right; place 1. [1, 2, 4, 5, 6, 3].
i=5: key=3. Slide 6, 5, 4 right; place 3. [1, 2, 3, 4, 5, 6].

Sorted.

Big O

Best case: $O (n)$ — already sorted input. The inner while loop never executes (each element is already in place). Just $n - 1$ comparisons total.
Average case: $O (n^{2})$ — on average, each element shifts halfway through the sorted prefix.
Worst case: $O (n^{2})$ — reverse-sorted input. Each element shifts all the way to the front.

The $O (n)$ best case is the killer feature: insertion sort is adaptive. On nearly-sorted input, it’s nearly linear. This is why it’s heavily used as a building block.

Properties

Stable: yes. Equal elements never get swapped past each other (the comparison is strict >).
In place: $O (1)$ extra space.
Online: can sort a stream — given a new element, insert it into the existing sorted output.

When to use

Practical uses:

Small arrays. Insertion sort beats $O (n lo g n)$ algorithms for small $n$ — the typical cutoff is in the 16–64 range, but the exact value is library-specific (libstdc++ std::sort switches at 16, Java’s Arrays.sort for primitives uses 47, Python’s Timsort uses 32–64). Constants are small and there’s no recursive overhead.
Nearly sorted arrays. When data is mostly sorted, insertion sort’s $O (n)$ best case wins.
As a subroutine. Most $O (n lo g n)$ sorts use insertion sort for small subarrays — for example, Quicksort often switches to insertion sort once recursion hits sub-arrays of size ≤ 16. Hybrid sorts like Timsort mix insertion sort with Merge sort heavily.
Within Bucket sort: each bucket is small and often nearly sorted, so insertion sort is a natural choice for sorting individual buckets.
Within Shell sort: shell sort is essentially repeated insertion sort with progressively smaller gaps. The final gap-1 pass is plain insertion sort on near-sorted data.

Comparison with other quadratic sorts

Sort	Best	Average	Worst	Stable	Adaptive
Insertion	O(n)	O(n²)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	O(n²)	No	No
Bubble	O(n) (with early exit)	O(n²)	O(n²)	Yes	Somewhat

Insertion sort wins among the quadratic sorts on every metric except worst-case swaps (selection sort does fewer). It’s the default choice when you want a simple sort that’s also fast on small or nearly-sorted data.

For the better large-array alternatives, see Quick sort, Merge sort, Heap sort.

Idriss Rami — Notes

Explorer