What insertion sort does
Think of sorting playing cards in your hand: you take a new card, look left through the sorted cards, slide every larger card one place to the right, and drop the new card into the gap.
- Treat the left part of the array as sorted; at first it holds only the first number.
- Take the next number as the key and leave a hole where it was.
- Compare leftwards: every number larger than the key shifts one place right, and the hole moves left.
- Stop at a number that is not larger than the key (or at the left edge) and put the key into the hole.
- Repeat until every number has been placed.
Why the best case is only O(n)
If the data is already sorted, each key is compared with just one neighbour and stops immediately, with no shifts. Try the “Best case” button above: n − 1 comparisons and 0 shifts.
The “Worst case” is a fully reversed array: every key travels all the way to the left, giving n(n − 1) / 2 comparisons and shifts.
Complexity
| Best | O(n) |
|---|---|
| Average | O(n²) |
| Worst | O(n²) |
| Extra space | O(1) |
| Stable | Yes |
FAQ
- Is insertion sort faster than bubble sort?
- Both are O(n²) on average and in the worst case, but insertion sort is usually faster because it shifts elements instead of repeatedly swapping them, and it approaches O(n) on nearly sorted data.
- When is insertion sort a good choice?
- When the input is small or already nearly sorted. Many standard libraries switch to insertion sort for small sub-ranges.
- Is insertion sort stable?
- Yes. It never moves an element past an equal one, so equal elements keep their relative order.