Overview
Insertion Sort grows a sorted region at the front of the array. It takes the next element and inserts it into its correct place among the already-sorted elements, shifting larger ones aside — much like sorting a hand of playing cards.
How Insertion Sort works
- Start with the first element considered sorted.
- Take the next element (the 'key') from the unsorted part.
- Shift every larger sorted element one slot to the right to open a gap.
- Drop the key into the gap, then repeat for the remaining elements.
When to use it
- Small arrays and nearly-sorted data, where it approaches O(n).
- Online sorting — it can sort a stream as elements arrive.
- As the base case inside hybrid sorts (e.g. the small-subarray cutoff in Quick Sort / Timsort).
Complexity analysis
In the worst case (reverse-sorted) every key shifts past all predecessors, giving O(n²). On nearly-sorted input few shifts happen, so it approaches O(n) — its best-case strength. It is in-place and stable.
Frequently asked questions
When is Insertion Sort actually a good choice?
For small or almost-sorted arrays it is often faster than O(n log n) sorts because of low overhead and its O(n) best case. That is why libraries fall back to it for tiny subarrays.
Is Insertion Sort stable?
Yes — it only shifts elements strictly greater than the key, so equal elements keep their relative order.