Insertion Sort: Shifting, Gaps and Cost
Grow a sorted prefix one value at a time: lift the next value out, shift larger ones right, and drop it into the gap.
Building a Sorted Prefix
Insertion sort treats a[0..i-1] as already sorted and inserts a[i] into its correct place within that prefix. One round looks like this:
- Lift copy
a[i]into a temporary. That slot is now a gap you are free to overwrite. - Scan left compare the key against each value in the sorted prefix, walking backwards.
- Shift every value larger than the key moves one slot right, dragging the gap left with it.
- Drop the first value not greater than the key stops the scan. Write the key into the gap.
This is exactly how most people sort a dealt hand of cards: the cards already held are in order, you take the next one, slide it left past every larger card, and drop it in.
The distinction from selection sort is important. Selection sort's prefix contains values in their final positions — nothing later can disturb them. Insertion sort's prefix is sorted relative to itself, but a later value can still land in the middle of it. Both invariants are useful; confusing them is a common exam error.
- Invariant:
a[0..i-1]is sorted, though not necessarily final - Round
iinserts one value into that sorted prefix - Start at
i = 1— a single element is already sorted - The prefix grows by exactly one element per round
Shifting Beats Swapping
A naive version swaps the key leftward one position at a time. Each swap costs three writes (temp, left, right), so a key moving k places costs 3k writes.
The standard version does better. Copy the key into a temporary, then shift each larger value one slot right — one write each — and finally write the key once into the gap. Moving k places now costs k + 1 writes rather than 3k.
That is roughly a threefold reduction in memory traffic for identical comparisons, and it is why insertion sort outperforms bubble sort on real hardware despite sharing the same O(n²) bound. The inner loop is also branch-predictable and cache-friendly: it walks backwards through contiguous memory doing one comparison and one move.
| Approach | Writes to move k places | Inner loop |
|---|---|---|
| Repeated swap | 3k | compare, then three-way swap |
| Shift and place | k + 1 | compare, then one move |
| Bubble sort pass | 3 per swap | compare every adjacent pair |
- Save the key first, then shift — do not swap in the inner loop
- The gap travels left; the key drops in once at the end
- Fewer writes matter more than comparison count on modern CPUs
- The loop stops as soon as a value less than or equal to the key appears
Sort with insertion sort
def insertion_sort(values):
for i in range(1, len(values)):
key = values[i] # lift the value out, leaving a gap
j = i - 1
# shift every larger value one slot right
while j >= 0 and values[j] > key:
values[j + 1] = values[j]
j -= 1
values[j + 1] = key # drop the key into the gap
return values
print(insertion_sort([2, 5, 9, 3, 8]))
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& values) {
for (std::size_t i = 1; i < values.size(); ++i) {
const int key = values[i]; // lift the value out, leaving a gap
int j = static_cast<int>(i) - 1;
// shift every larger value one slot right
while (j >= 0 && values[j] > key) {
values[j + 1] = values[j];
--j;
}
values[j + 1] = key; // drop the key into the gap
}
}
int main() {
std::vector<int> values {
2, 5, 9, 3, 8
};
insertionSort(values);
for (int v : values) std::cout << v << ' ';
std::cout << '\n';
}import java.util.Arrays;
public class InsertionSort {
static void insertionSort(int[] values) {
for (int i = 1; i < values.length; i++) {
int key = values[i]; // lift the value out, leaving a gap
int j = i - 1;
// shift every larger value one slot right
while (j >= 0 && values[j] > key) {
values[j + 1] = values[j];
j--;
}
values[j + 1] = key; // drop the key into the gap
}
}
public static void main(String[] args) {
int[] values = {2, 5, 9, 3, 8};
insertionSort(values);
System.out.println(Arrays.toString(values));
}
}Step through it
Running on [2, 5, 9, 3, 8]
On paper: Inserting Into the Prefix
Take [2, 5, 9, 3, 8]. Four rounds, starting at index 1:
- Round 1 key = 5. Compare with 2: not larger, stop immediately. Nothing moves. One comparison.
- Round 2 key = 9. Compare with 5: not larger, stop. Nothing moves. One comparison.
- Round 3 key = 3. Shift 9 right, shift 5 right, stop at 2. Write 3 at index 1 →
[2, 3, 5, 9, 8]. - Round 4 key = 8. Shift 9 right, stop at 5. Write 8 at index 3 →
[2, 3, 5, 8, 9]. - Done 7 comparisons and 5 writes, against bubble sort's 9 comparisons on the same size.
Note what an exam answer must show: the comparison that fails is what stops each scan. On nearly sorted input it fails immediately, which is exactly why such input is cheap.
- Show the key lifted out and the gap it leaves behind
- Each shift is one write; the key is written once at the end
- The scan stops at the first value not greater than the key
- Total here: 6 comparisons, far below the worst case of 10
Why the Best Case Is Linear
On already-sorted input every round performs exactly one comparison — the key is not smaller than its left neighbour, so the inner loop never runs. That is n−1 comparisons and zero shifts: Θ(n) total.
The general result is sharper than 'best case linear'. Insertion sort runs in O(n + d) where d is the number of inversions — pairs out of order. Each shift removes exactly one inversion, so the work is proportional to how unsorted the input actually is.
That makes it genuinely adaptive, and it explains its real-world role. Standard library sorts (including introsort in C++ and Timsort in Python and Java) recurse only until a subarray is small — typically 16 to 32 elements — then finish with insertion sort, because at that size a small nearly-sorted array beats the overhead of another recursive call.
| Input | Comparisons | Shifts | Time |
|---|---|---|---|
| Sorted | n−1 | 0 | Θ(n) |
| Nearly sorted (d inversions) | n + d | d | Θ(n + d) |
| Random | ≈ n²/4 | ≈ n²/4 | Θ(n²) |
| Reversed | n(n−1)/2 | n(n−1)/2 | Θ(n²) |
- Work is proportional to the inversion count, not just to n
- Sorted input costs one comparison per element
- Stable, because the scan stops at equals rather than passing them
- Used as the base case inside quick sort and Timsort
Choosing Among the Simple Sorts
For arrays, insertion sort is the one to reach for. It is stable, in-place, adaptive, and has the smallest constant factor of the three quadratic sorts — bubble sort does three times the writes, and selection sort cannot adapt at all.
Its one structural weakness is the shift. On a linked list, shifting means walking pointers, so insertion into a list is done by relinking rather than moving values — the same algorithm, a different cost model.
Above a few dozen elements the quadratic term wins regardless of constants, and the correct choice becomes merge sort for guaranteed O(n log n) and stability, or quick sort for raw in-place speed.
- Best simple sort for small or nearly sorted arrays
- Stable and in-place, with an O(n) best case
- Crosses over to O(n log n) sorts somewhere around 16–32 elements
- Heap sort gives O(n log n) without recursion or extra memory