About Insertion Sort
Insertion Sort grows a sorted region at the front of the array. For each new element, it walks leftward through the already-sorted region, swapping the element with its neighbour until it reaches its correct position. It is stable, in-place, and O(n²) in the worst case, but O(n) on nearly-sorted input — which makes it excellent for small or almost-sorted arrays. It is also the algorithm most people use instinctively when sorting a hand of playing cards.
Complexity Analysis
- Time Complexity
- O(n²)
- Space Complexity
- O(1)
- Difficulty
- beginner
Key Concepts
Growing a Sorted Region
At the start of iteration i, the sub-array array[0..i-1] is already sorted. Insertion Sort places array[i] into that region so that array[0..i] becomes sorted. The invariant holds until the whole array is sorted.
Stability
Insertion Sort is stable: it only swaps when the left element is strictly greater than the right, so equal elements never cross each other and keep their original relative order.
Adaptive Performance
On a nearly-sorted array, most elements are already in place, so the inner loop rarely runs. This gives O(n) best-case time — one of the reasons Insertion Sort is used as the base case inside faster hybrid sorts like Timsort.
Common Pitfalls
Confusing it with Selection Sort
Insertion Sort inserts the next element into the sorted region; Selection Sort repeatedly selects the minimum of the unsorted region. Insertion Sort is adaptive and stable; Selection Sort is neither.
Off-by-one in the inner loop
The inner loop must stop at j = 0. Comparing array[j - 1] when j = 0 reads out of bounds. The condition j > 0 guards against this.