Insertion sort is a comparison-based sorting algorithm that builds the sorted array one element at a time by inserting each unsorted element into its correct position among the already-sorted elements — achieving O(n) on nearly-sorted data, Θ(n²) average, and O(1) space.
Insertion sort builds a sorted sequence one element at a time by taking each new element and inserting it into its correct position among the already-sorted elements — exactly how you would sort playing cards in your hand.
How it works
Divide the array into a sorted left part and an unsorted right part. Initially the sorted part has just one element (the first). Take the next element from the unsorted part, scan backwards through the sorted part to find its correct position, shift elements right to make room, and insert. Repeat until the unsorted part is empty.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to insert
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift right
j -= 1
arr[j + 1] = key # insert in correct position
return arr
print(insertion_sort([5, 2, 8, 1, 9, 3])) # [1, 2, 3, 5, 8, 9]void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}Complexity
| Case | Time | Space | Notes |
|---|---|---|---|
| Best (sorted input) | Θ(n) | O(1) | Inner while loop never executes |
| Average (random input) | Θ(n²) | O(1) | ~n²/4 comparisons |
| Worst (reverse sorted) | Θ(n²) | O(1) | Every element shifts all the way left |
When insertion sort wins
For small arrays (n ≤ 10–16), insertion sort is faster than merge sort or quicksort in practice. Reasons: (1) the constant factor is tiny — one comparison, one assignment per step; (2) no recursion overhead; (3) excellent cache behaviour — accesses nearby memory. This is why Timsort uses insertion sort for subarrays of size ≤ 64, and Java's Arrays.sort() uses insertion sort for n ≤ 7.
Near-sorted input: where insertion sort shines
If the input is almost sorted — each element is at most k positions away from its final position — insertion sort runs in O(nk) time. For k=1 (each element displaced by at most 1), insertion sort is O(n). This is why Timsort detects natural sorted runs and uses insertion sort to extend them.
Inversions: the formal measure of disorder
An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. A sorted array has 0 inversions; a reverse-sorted array has n(n-1)/2 inversions. Insertion sort's running time is exactly Θ(n + I) where I is the number of inversions: each comparison either resolves an inversion (removes one) or determines we've reached the insertion point. The average number of inversions in a random permutation is n(n-1)/4, giving average Θ(n²).
Comparison vs. Java's implementation
Java's Arrays.sort(int[]) uses dual-pivot quicksort for n > 47. For 5 ≤ n ≤ 47, it uses insertion sort. For n ≤ 4, it uses simple comparisons (unrolled insertion sort). The threshold 47 is empirically tuned — below it, insertion sort's small constant beats quicksort's recursive overhead.
Binary insertion sort
Binary insertion sort replaces the linear scan with a binary search to find the insertion position, reducing comparisons to O(n log n) total. But the number of shifts (assignments) remains Θ(n²). Since modern CPUs make shifts cheap (sequential memory access, cache-friendly) but comparisons less so, binary insertion sort is sometimes faster in practice for medium n despite identical asymptotic complexity.
Insertion sort and the inversion lower bound
Any sort algorithm that works by adjacent swaps must perform at least as many swaps as the number of inversions in the input. Insertion sort achieves this minimum — it removes exactly one inversion per swap (each shift moves the key one position closer to its final location). Bubble sort also removes one inversion per swap but does more comparisons. This makes insertion sort the optimal adjacent-swap sort.
Shell sort: a generalisation
Shell sort (Donald Shell, 1959) is a generalisation of insertion sort that first compares elements far apart, then progressively closes the gap. For gap sequence h = 3k+1 (Knuth, 1973): 1, 4, 13, 40, … Shell sort runs in O(n4/3) with this sequence — better than O(n²). For optimally chosen gap sequences, the complexity reaches O(n log² n). No O(n log n) gap sequence is known for Shell sort — finding the optimal sequence is an open problem.
Cormen, T. H. et al. (2022). CLRS (4th ed.), §2.1 — Insertion sort. Knuth, D. E. (1998). TAOCP Vol. 3, §5.2.1 — Sorting by insertion. Shell, D. L. (1959). "A high-speed sorting procedure." CACM 2(7).