algorithms · medium

Insertion Sort

Insertion sort builds the result one element at a time, shifting larger elements right to open a slot for each new value — like sorting a hand of cards. It's O(n^2) in the worst case but O(n) on nearly-sorted input, stable, and in-place, which is exactly why introsort/std::sort switches to it for small subarrays.

The code

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { // shift larger elements right
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key; // drop key into the gap
    }
}

What this lesson walks through

1. 01Insertion sort — the unsorted array
2. 02Insert a[1] = 3
3. 03Insert a[2] = 8
4. 04Insert a[3] = 1
5. 05Insert a[4] = 9
6. 06Sorted

Insertion sort grows a sorted prefix one element at a time, sliding each new value left into its correct spot — exactly how you sort a hand of cards.