Insertion Sort

Sorting O(n²) O(1)

Grows a sorted prefix one element at a time, shifting larger values right until the new element fits.

Idle

Starting Insertion Sort on 8 elements.

InvariantA[0..1-1] is sorted. The key is held aside, so the gap in the array is not a lost value.

1/49

comparisons0moves0i0j0key0

compareswapshiftselectsorted

insertion-sort.c

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];
            j--;
        }
        arr[j + 1] = key;
    }
}

How Insertion Sort works

Keep the left part sorted. Take the next element, shift everything larger one step right, and drop it into the gap — the way you sort playing cards in your hand.

Best case

Already (or nearly) sorted — each element shifts at most a step: O(n).

Worst case

Reverse-sorted — every element travels all the way left: O(n²).

When to use it

Small or nearly-sorted arrays; the standard finishing pass inside hybrid sorts like Timsort.