Insertion Sort
Grows a sorted prefix on the left and inserts each new element into the right slot.
- Comparisons 0
- Shifts 0
- Placements 0
- sorted indices 1
- active
- compare
- swap
- sorted
Pseudocode
1 for i from 1 to n - 1
2 key = a[i]
3 j = i - 1
4 while j >= 0 and a[j] > key
5 a[j + 1] = a[j]
6 j = j - 1
7 a[j + 1] = key
Step log
How it works, runtime and memory
Insertion Sort treats the array like a deck of cards: the sorted prefix lives on the left, the unsorted tail on the right. In every step it picks the first unsorted element (the key) and compares it from right to left with all values in the sorted prefix. As long as a value is larger than the key, that value is shifted one position to the right. As soon as a smaller value (or the array start) is found, the key is placed into the resulting gap. The sorted prefix grows by one each iteration. The best case is an already-sorted input where the inner check exits immediately, giving linear best-case runtime O(n). In the average and worst case each element may compare and shift against i predecessors, leading to quadratic total runtime O(n^2). Insertion Sort runs in-place and uses only constant extra memory O(1). Equal elements keep their order, so the algorithm is stable.
Complexity
- Best case
O(n) - Average case
O(n^2) - Worst case
O(n^2) - Extra space
O(1)
When to use it
Very strong on small arrays with fewer than roughly 20 elements and on nearly sorted data, where the runtime drops to linear. That is why hybrid sorts like Timsort fall back to Insertion Sort once the recursive sub-ranges are small enough.