Step by step
The example above, written out — the same steps the animation plays.
- 1Start. Insertion sort grows a sorted part on the left, one card at a time — like sorting a hand of cards.
- 2Pick up 3. 3 is the next card. Everything to its left is already sorted.
- 3Compare 3 with 5. 5 > 3, so 5 shifts right to make room.
- 45 shifts right. 5 moves one place right; 3 slides left.
- 53 inserted. The first 2 values are now sorted.
- 6Pick up 8. 8 is the next card. Everything to its left is already sorted.
- 7Compare 8 with 5. 5 ≤ 8: 8 belongs right here.
- 88 inserted. The first 3 values are now sorted.
- 9Pick up 2. 2 is the next card. Everything to its left is already sorted.
- 10Compare 2 with 8. 8 > 2, so 8 shifts right to make room.
- 118 shifts right. 8 moves one place right; 2 slides left.
- 12Compare 2 with 5. 5 > 2, so 5 shifts right to make room.
- 135 shifts right. 5 moves one place right; 2 slides left.
- 14Compare 2 with 3. 3 > 2, so 3 shifts right to make room.
…and 27 more steps — press Play above to watch them all.
What's happening?
- The first value on its own counts as sorted.
- Each next value is "picked up" and compared with the sorted values to its left; bigger ones shift right to make room.
- When a smaller (or equal) value is reached, the picked-up value drops into the gap.
Complexity
- Time
- O(n²) worst and average · O(n) when already nearly sorted
- Space
- O(1) — sorts in place
Where you'll meet it
Small or nearly-sorted data. Real libraries (Java's and Python's sorts, TimSort) switch to insertion sort for short runs because it is so fast there.
Common mistake
Assuming it is always slow. On nearly sorted input it does almost no work — often beating "faster" algorithms.
FAQ
Is insertion sort stable?
Yes. Equal values never pass each other, so their original order is kept.
Why is it fast on nearly sorted data?
Each value only moves as far as it is out of place. If nothing is far out of place, there is little to shift.
Insertion sort vs bubble sort?
Both are O(n²), but insertion sort usually does far fewer moves and is preferred in practice.