Insertion Sort Visualization
Take the next element, slide it backwards past everything larger, drop it in place. This is how you sort a hand of cards, and unlike its O(n squared) siblings it earns its keep in production: std::sort switches to insertion sort once a partition gets small, because on short or nearly-sorted runs it genuinely is the fastest thing available.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
void insertionSort(vector<int>& a) {
int n = a.size();
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main() {
vector<int> a = {12, 11, 13, 5, 6};
insertionSort(a);
for (int x : a) cout << x << ' ';
return 0;
}Shifts larger elements right one at a time rather than swapping, so each element is written once per position it passes.
How it works, step by step
The prefix is always sorted
Before iteration i, a[0..i-1] is sorted among itself — though not necessarily in final position, since a later element may still need to slide into the middle of it. The loop starts at 1 because a single element is trivially sorted.
key is saved before the shifting starts
a[i] is copied into key first, which frees that slot. The while loop then overwrites it with the shifted neighbour. Without the copy, the first shift would destroy the value you are trying to place.
Shifting, not swapping
Each larger element moves one slot right, opening a gap that travels leftwards. This is roughly half the memory traffic of a swap-based version, which does three writes per step instead of one — the reason this beats bubble sort on identical comparison counts.
The while loop stops at the right place twice over
It exits either because j hit -1 (key is the new smallest) or because a[j] <= key (the correct spot). Both cases leave the gap at j + 1, which is why a single a[j + 1] = key handles them both.
Nearly-sorted input barely moves
If each element is already close to its final position, the while loop runs a couple of iterations and stops. Total work becomes O(n + d) where d is the number of inversions, so an almost-sorted array is handled in near-linear time.
Complexity
The inner loop runs once per inversion involving the current element, so a reversed array costs the full n squared while a sorted one costs a single comparison per element; that adaptivity is exactly why library sorts fall back to it below ~16 elements.
Common bugs
Writing a[j] = key instead of a[j + 1] = key
When the while loop exits, j points one slot to the left of the gap — either at the element that is <= key, or at -1. Writing to a[j] either clobbers a correctly placed value or, when j is -1, corrupts memory before the array. The gap is always at j + 1.
Checking a[j] > key before checking j >= 0
Reversing the operands to while (a[j] > key && j >= 0) reads a[-1] when key is the smallest element seen so far. C++ short-circuits left to right, so the bounds test must come first. This crashes only on inputs with a new minimum, which is why it survives casual testing.
Starting the outer loop at i = 0
Then j starts at -1, the while loop is skipped, and a[0] = key rewrites the element with itself. Harmless, but it signals a misunderstanding: the first element is the initial sorted prefix, not something to insert.
Using >= in the shift condition
while (j >= 0 && a[j] >= key) keeps shifting past elements equal to key, placing the new element before its equals and destroying stability. It also does strictly more work. Insertion sort is stable precisely because it stops at the first element that is not greater.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why is insertion sort used inside real sorting libraries?
Because for small arrays it is genuinely fastest. It has almost no per-element overhead, excellent cache behaviour since it touches adjacent memory, and it exploits partial order. Implementations of std::sort run introsort down to a threshold of roughly 16 elements and then finish the whole array with one insertion sort pass.
What is the difference between insertion sort and bubble sort?
Insertion sort takes one element and moves it directly to its correct place in the sorted prefix, shifting others aside. Bubble sort repeatedly swaps adjacent pairs across the whole array. They have the same worst-case complexity, but insertion sort does about a third of the writes and adapts far better to nearly-sorted input.
When is insertion sort O(n)?
When the array is already sorted or nearly so. For each element the while loop tests a[j] > key once, finds it false, and exits immediately — so the total is n-1 comparisons and zero shifts. More generally the running time is proportional to the number of inversions in the input.
Is insertion sort stable?
Yes, provided the shift condition is a strict a[j] > key. Elements equal to the one being inserted are never shifted, so the new element settles after its equals and relative order is preserved. Using >= breaks this.