What is insertion sort?
Insertion sort grows a sorted section one item at a time. Starting from the front, it takes the next unsorted
value — the key — and slides it backward past every value in the sorted prefix that's bigger
than it, until it lands in the exact spot that keeps the prefix in order.
- Sorted prefix
- The part of the array, starting at index 0, that is already in order
- Key
- The next unsorted value, about to be inserted into the sorted prefix
- Shift
- Moving a bigger value one slot right to make room for the key
Why insertion sort at all?
Picture sorting a hand of playing cards. You already hold a few cards in order. You pick up the next card from the table and slide it into your hand — past every card bigger than it — until it sits between the two cards it belongs among.
You never re-sort the cards already in your hand from scratch. Each new card only has to find its own spot, sliding past exactly as many cards as it needs to and no more.
Pick up the next card and compare it to the hand.
What kinds of problems does it solve?
Same idea underneath every variant: build the sorted section by inserting one value backward into place. What changes is where that mechanic gets applied.
The shift-and-insert mechanic
Compare the key against the sorted prefix from right to left. Every value bigger than the key slides one slot right. The moment you hit a value that's smaller — or run out of prefix — the key drops into that gap.
Key = 1 (index 4). Sorted prefix so far: [2, 4, 5, 6].
Adaptive on nearly-sorted input
If the key is already bigger than everything to its left, it needs zero shifts — one comparison and it stays put. On data that's already close to sorted, most insertions cost almost nothing, so the whole pass finishes close to O(n).
Key=2. Compare with 1 — already bigger, 0 shifts needed.
Stable — equal values keep their order
When the key ties with a value already in the sorted prefix, insertion sort stops shifting and drops the key right after it — never before. Two equal values never swap places, so their original order survives the sort.
Key = 1 (b). Compare with 3 (a).
Two things worth knowing
Everything above comes down to two mechanics: how a single insert works, and why that makes the whole algorithm adaptive.
Shift-and-insert
Walk backward from the key's position. While the value to the left is bigger, copy it one slot right and step left. Stop and write the key into the gap the moment you find a smaller value or reach the start of the array.
Key = 3. Start comparing at the end of the sorted prefix.
function shiftAndInsert(arr: number[], key: number, start: number): void {
let i = start;
while (i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i]; // shift the bigger value right
i--;
}
arr[i + 1] = key; // drop the key into the gap
}
Why it's adaptive
Best case: the input is already sorted. Every key only ever needs one comparison against its immediate left neighbor, which is already smaller — so no shifting happens at all, and the whole pass runs in O(n).
Key=2. One comparison against 1 — already bigger. 0 shifts.
function insertionSort(arr: number[]): number[] {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // best case: this loop never runs
}
return arr;
}
Where it works — and where it breaks
Insertion sort's cost is entirely about how far each key has to travel. Nearly-sorted input means short trips. Reverse-sorted input means every key travels all the way to the front.
Fast on nearly-sorted data
Only a few keys are out of place, so most insertions do zero or one shift. Total work stays close to O(n) — this is exactly why hybrid sorts like Timsort switch to insertion sort for small, mostly-sorted runs.
Key=3. Sorted prefix: [1, 2, 4].
Slow on reverse-sorted data
Every new key is smaller than everything already placed, so it has to shift past the entire sorted prefix. That's up to n shifts per key, and O(n²) comparisons overall in the worst case.
Key=4. Shifts past 5 — 1 shift.