Insertion sort is the algorithm most people use by hand when sorting playing cards. It is quadratic in the worst case, yet it is still in production code everywhere because it is adaptive, stable, in-place and has almost no overhead. This page traces it step by step, explains its adaptive behaviour, and shows where it is used inside larger algorithms.
Insertion sort builds a sorted prefix one element at a time, shifting each new element back to its correct position. It is fast on small or nearly-sorted inputs and is the inner sort used by Timsort, Introsort, and many hybrid algorithms.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n) |
Θ(n²) |
O(n²) |
O(1) |
For i from 1 to n−1: take element arr[i] and slide it leftward, swapping with each larger element on its left, until it finds its slot. The first i elements stay sorted as an invariant. On nearly-sorted data each element shifts only a constant number of times — that's the O(n) best case.
def insertion_sort(arr):
"""In-place insertion sort."""
for i in range(1, len(arr)):
x = arr[i]
j = i - 1
while j >= 0 and arr[j] > x:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = x
return arr
print(insertion_sort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]The loop invariant is that positions 0 to i-1 are sorted. At step i the algorithm lifts out a[i], shifts every larger element in the prefix one slot right, and drops the lifted value into the gap. In the trace, inserting 1 at i=4 shifts four elements, which is the expensive case; inserting 6 at i=3 shifts nothing because 6 is already larger than everything before it.
The number of shifts equals the number of inversions in the input, that is, pairs (i, j) with i < j and a[i] > a[j]. That gives the precise complexity: O(n + I) where I is the inversion count. Sorted input has I = 0 and runs in linear time; reversed input has I = n(n-1)/2.
Binary insertion sort finds the insertion point with binary search, cutting comparisons to O(n log n). It still shifts O(n^2) elements, so it helps only when comparisons are expensive (for example, comparing long strings or objects with Python __lt__). Python's bisect.insort does exactly this. Another micro-optimisation moves the minimum to position 0 first so the inner loop no longer needs the j >= 0 bound check.
import bisect
def binary_insertion_sort(a):
out = []
for x in a:
bisect.insort_right(out, x) # insort_right keeps it stable
return out
def insertion_sort_count(a):
"""Return the sorted list and the number of shifts (= inversions)."""
a, shifts = list(a), 0
for i in range(1, len(a)):
key, j = a[i], i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
shifts += 1
a[j + 1] = key
return a, shifts
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
print(insertion_sort_count([5, 2, 4, 6, 1, 3])) # ([1..6], 9)The second function counts shifts, which is a handy way to measure how far from sorted a dataset is. Note the strict > comparison in the inner loop: using >= would move equal elements past each other and make the sort unstable.
Divide-and-conquer sorts have recursion and bookkeeping overhead that dominates for tiny subarrays. Production implementations therefore stop recursing below a small threshold and finish with insertion sort. Timsort extends short natural runs to a minimum run length (32 to 64) with binary insertion sort; introsort-based std::sort implementations leave partitions of about 16 elements unsorted and run one insertion pass at the end; Shell sort is insertion sort applied over a shrinking sequence of gaps.
| Input | Insertion sort | Better choice |
|---|---|---|
| Fewer than ~20-50 items | Often fastest | - |
| Nearly sorted, few inversions | Close to O(n) | - |
| Online: items arrive one at a time | Natural fit | Heap or balanced tree for large n |
| Large random data | O(n^2), avoid | Timsort, Mergesort |
Insertion sort also has useful structural properties beyond speed. It is stable, so records with equal keys keep their original order, which matters when sorting by one column after another. It is in-place, needing only one temporary variable. It is online, meaning it can sort a stream as items arrive without seeing the whole input first. Few other algorithms have all three properties at once, which is why it survives as the base case of more sophisticated sorts.
>= in the inner loop.