Insertion Sort
Imagine sorting a hand of playing cards as they are dealt to you, one at a time. You hold a sorted fan in your left hand. For each new card, you slide it leftward. It settles into its correct position among the cards you already hold. By the time the last card is dealt, your entire hand is sorted. This is not a metaphor invented for teaching. It is a literal, correct description of insertion sort, one of the oldest and simplest sorting algorithms in computer science. Insertion sort matters because it is the cleanest vehicle for teaching loop invariants. Loop invariants are the single most powerful tool for proving that an algorithm is correct. Its structure — grow a sorted region one element at a time — appears again and again in more advanced designs. This includes the recursive merges of Merge Sort, the partition-based splitting of Quicksort, and the bucket-then-insert strategy of Bucket Sort. Understanding insertion sort deeply pays dividends far beyond the algorithm itself. In real systems, insertion sort is far from obsolete. Its low overhead per element and excellent performance on small or nearly-sorted arrays make it the default fallback. It sits inside production sorting libraries. Timsort (used in Python and Java) and introsort variants (used in C++'s `std::sort`) both switch to insertion sort. This happens once a recursive subproblem shrinks below a small threshold (commonly 16–32 elements). At that scale, insertion sort's low constant factors beat the overhead of recursive divide-and-conquer. This article builds insertion sort from first principles. It covers the exact mechanics of the "shift and insert" step, a rigorous loop-invariant proof of correctness, and a careful derivation of best-case and worst-case running time. It also includes a full trace on a nontrivial input. Finally, it explores the historical and practical context. This context explains why this simple algorithm still ships inside modern software.
- Insertion sort builds a sorted prefix of the array one element at a time, inserting each new element into its correct place among those already sorted.
- It sorts in place using O(1) extra space, and is a stable sort — equal elements keep their relative order.
- Best case is O(n) on already-sorted input; worst and average case are O(n²) on reverse-sorted or random input.
- Correctness follows from a loop invariant: after each outer iteration, `A[0..i]` is a sorted permutation of the original first `i+1` elements.
- It is the practical default for small subarrays (n ≲ 32), embedded inside hybrid sorts like Timsort and introsort.
- It foreshadows the design ideas behind Selection Sort, Merge Sort, and Bucket Sort.
Insertion sort maintains a growing sorted prefix and repeatedly shifts each new element leftward past everything larger than it, so correctness of the whole array reduces to correctness of one loop invariant.
The idea
Insertion sort operates by dividing the array conceptually into two contiguous regions: a sorted prefix on the left and an unprocessed suffix on the right. Initially the sorted prefix contains just the first element (a single element is trivially sorted), and the unprocessed suffix is everything else. The algorithm repeatedly takes the leftmost element of the unprocessed suffix — call it the key — and inserts it into the correct position within the sorted prefix, shifting larger elements one slot to the right to make room. After each such step the sorted prefix has grown by exactly one element, and the suffix has shrunk by one. When the suffix is empty, the whole array is sorted. This is fundamentally different from Selection Sort, which also grows a sorted prefix but does so by repeatedly finding the minimum of the remaining suffix and swapping it into place — a "select then place" strategy, versus insertion sort's "take the next element and place it" strategy. Insertion sort's per-step cost depends on how far the key must travel (data-dependent), while selection sort's per-step cost is always a full scan of the remaining suffix (data-independent). This distinction is exactly why insertion sort has a fast best case and selection sort does not. The key operation — shifting elements right to make room for an insertion — is performed with a linear scan comparing the key against elements immediately to its left, moving them right as long as they exceed the key. This shift-based insertion is what makes the sort stable: when the key is equal to an element already in the sorted prefix, the scan stops (it does not shift equal elements past the key), so equal elements retain their original relative order. Stability is a property that later matters when sorting records by a secondary key, or when insertion sort is embedded as the final finishing pass of a stable merge-based sort.
How it works
The algorithm processes indices `i = 1, 2, ..., n-1` in order. At the start of iteration `i`, the subarray `A[0..i-1]` is already sorted (this is the invariant we will prove). The element `A[i]` is saved as the `key`, and then compared against the sorted elements to its left, moving each one that is strictly greater than `key` one position to the right, until we find the correct resting place for `key` (or run off the left end of the array). ```pseudocode INSERTION-SORT(A, n): // A is an array indexed 0..n-1 for i = 1 to n - 1: key = A[i] j = i - 1 // Shift elements of A[0..i-1] that are greater than key // to the right by one position, opening a gap for key. while j >= 0 and A[j] > key: A[j + 1] = A[j] j = j - 1 A[j + 1] = key // insert key into the opened gap return A ``` Two design details deserve emphasis. First, the comparison `A[j] > key` (strictly greater than) is what makes the sort stable: an element equal to `key` is not shifted, so `key` is inserted immediately after it, preserving original order among equal elements. Second, the `while` loop's second condition `A[j] > key` is only evaluated when `j >= 0` is true — the pseudocode relies on short-circuit evaluation, and this ordering is not cosmetic: without it, the algorithm would read `A[-1]`, an out-of-bounds access, whenever `key` turns out to be the smallest element seen so far. The diagram below shows one array undergoing a single outer iteration: the key `5` is lifted out, elements `9` and `7` (both greater than `5`) are shifted right, and `5` is dropped into the vacated slot.
Complexity & correctness
Correctness — the loop invariant. Define the invariant I(i), checked at the top of each outer-loop iteration: > At the start of the iteration with outer-loop variable `i`, the subarray `A[0..i-1]` consists of the same elements originally found there, but rearranged into sorted order. We verify the three standard parts of a loop-invariant proof.
- Initialization. Before the first iteration, `i = 1`, so `A[0..0]` is a single-element subarray. A one-element array is trivially sorted, so I(1) holds.
- Maintenance. Assume I(i) holds: `A[0..i-1]` is sorted. The inner `while` loop scans right-to-left from position `i-1`, shifting each element greater than `key = A[i]` one slot right, and stops at the first element that is `<= key` (or the array start). Because `A[0..i-1]` was sorted, this scan correctly identifies the unique insertion point for `key`: everything shifted right was `> key`, everything left in place is `<= key`. After inserting `key` into the gap, `A[0..i]` contains exactly the same multiset of elements as before (a permutation — nothing was added, removed, or duplicated, only moved), and it is now sorted. This establishes I(i+1).
- Termination. The outer loop runs while `i <= n-1`, so it terminates when `i = n`. At that point I(n) holds: `A[0..n-1]`, the entire array, is a sorted permutation of the original array. This is exactly the postcondition we need — the loop invariant, at termination, is the correctness proof.
This is the textbook illustration of why loop invariants work: they are like mathematical induction applied to a running program, with initialization playing the role of the base case and maintenance playing the role of the inductive step.
Time complexity. Let `n` be the array length. The outer loop runs `n - 1` times. For a fixed `i`, the inner `while` loop runs at most `i` times (it can shift past all of `A[0..i-1]`). Summing the worst case over all iterations: ``` T(n) = Σ_{i=1}^{n-1} i = (n-1)n / 2 = Θ(n²) ```
- Worst case — Θ(n²): occurs when the array is sorted in strictly decreasing order. Every key must shift past all previously sorted elements, so the inner loop always runs the maximum number of times.
- Best case — Θ(n): occurs when the array is already sorted in nondecreasing order. For every `i`, the very first comparison `A[i-1] > key` is false, so the inner `while` loop body never executes — each outer iteration costs O(1), giving a total of Θ(n).
- Average case — Θ(n²): for a uniformly random permutation, each key is expected to be greater than about half of the elements to its left, so the expected number of shifts at step `i` is Θ(i), and the sum is still Θ(n²) — only the hidden constant improves relative to the worst case.
Space complexity. Insertion sort is in-place: it uses only the input array plus a constant number of scalar variables (`key`, `i`, `j`), giving O(1) auxiliary space, independent of `n`. This is a real advantage over algorithms like standard Merge Sort, which needs Θ(n) auxiliary space for merging.
Honest tradeoffs. The Θ(n²) worst case makes insertion sort a poor choice for large, arbitrarily-ordered arrays — an O(n log n) comparison sort will always win asymptotically past some crossover size. But three properties keep it relevant: it is stable, it is adaptive (fast on nearly-sorted data, and "nearly sorted" is common in real workloads such as re-sorting after a small update), and it has very low constant overhead per element compared to recursive algorithms, which pay for recursive calls, index arithmetic, and cache-unfriendly divide steps.
Worked example
Trace `INSERTION-SORT` on the array `A = [5, 2, 9, 1, 7]` (indices 0–4). We show the array state at the start of each outer iteration, and detail the inner-loop shifts.
| `i` | `key` | State before insertion | Shifts performed | State after insertion |
|---|---|---|---|---|
| 1 | `A[1]=2` | `[5, 2, 9, 1, 7]` | `5 > 2` → shift `5` right | `[2, 5, 9, 1, 7]` |
| 2 | `A[2]=9` | `[2, 5, 9, 1, 7]` | `5 > 9`? No — loop body never runs | `[2, 5, 9, 1, 7]` |
| 3 | `A[3]=1` | `[2, 5, 9, 1, 7]` | `9>1` shift; `5>1` shift; `2>1` shift | `[1, 2, 5, 9, 7]` |
| 4 | `A[4]=7` | `[1, 2, 5, 9, 7]` | `9>7` shift; `5>7`? No — stop | `[1, 2, 5, 7, 9]` |
Step-by-step detail for the busiest iteration, `i = 3`, `key = 1`: ``` j=2: A[2]=9 > 1 → A[3]=9, j=1 array: [2,5,9,9,7] j=1: A[1]=5 > 1 → A[2]=5, j=0 array: [2,5,5,9,7] j=0: A[0]=2 > 1 → A[1]=2, j=-1 array: [2,2,5,9,7] j=-1: loop stops (j < 0) A[0] = key = 1 array: [1,2,5,9,7] ``` The final array is `[1, 2, 5, 7, 9]`, correctly sorted. Note the total number of inner-loop shifts across the whole run: `1 + 0 + 3 + 1 = 5` comparisons that led to a shift, plus a few more comparisons that failed and stopped the loop — consistent with this being neither the best case (already sorted) nor the true worst case (fully reversed), and therefore not a symmetry-hiding trivial example.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Off-by-one on loop bounds | Starting outer loop at `i = 0` instead of `i = 1` compares `A[0]` against a nonexistent `A[-1]` | Outer loop must start at `i = 1`; index 0 is the trivial one-element sorted base case |
| Reading `A[-1]` | Writing the inner condition as `A[j] > key and j >= 0` (order swapped) evaluates `A[j]` before checking `j >= 0` | Always put the bounds check first in a short-circuiting `and`/`&&` |
| Using `>=` instead of `>` | Shifting elements equal to `key` breaks stability — equal elements get reordered | Use strict `>` so equal elements are never shifted past the key |
| Forgetting `key` must be saved before shifting | Overwriting `A[i]` in place during the shift loses the value to be inserted | Copy `A[i]` into a scalar `key` before the `while` loop begins |
| Assuming O(n log n) behavior | Treating insertion sort as a general-purpose large-scale sort | Use it only for small `n`, nearly-sorted data, or as a finishing pass inside a hybrid sort |
Pioneers & history
Insertion sort predates modern computing entirely — it formalizes the same physical process people use sorting cards or filing documents by hand, and it was among the first sorting methods analyzed rigorously once computer science emerged as a discipline in the mid-20th century.
Origins · 1 minJohn von Neumann and how this was discovered
Von Neumann is widely credited with implementing one of the first sorting algorithms on an electronic stored-program computer, closely related to merge-based methods, as part of his foundational work on the architecture and programming of early digital computers. His broader contributions to computer architecture — the stored-program "von Neumann architecture" — created the very environment in which algorithms like insertion sort could be precisely specified, executed, and timed, setting the stage for formal algorithm analysis as a discipline.
Where this matters
Insertion sort's role in modern systems is less "the main algorithm" and more "the trusted finishing tool." Timsort, the sorting algorithm behind Python's `list.sort()` and Java's `Arrays.sort()` for objects, identifies naturally ordered runs in the data and uses a binary-search-augmented insertion sort to handle small runs directly, exploiting exactly the adaptive best-case behavior described above. Introsort, used in many C++ standard library implementations of `std::sort`, begins with quicksort-style partitioning, falls back to heapsort to guard against quicksort's own worst case, and switches to insertion sort once a partition shrinks below a small threshold, because at that size insertion sort's low constant overhead beats any asymptotically faster but heavier algorithm. Beyond general-purpose libraries, insertion sort's incremental, one-record-at-a-time structure matches real-time and streaming scenarios: maintaining a sorted leaderboard, a sorted event queue, or an online sorted index where elements arrive one at a time and must be placed correctly with minimal disruption. It is also the standard first example in courses that introduce Loop Invariants as a proof technique, precisely because its correctness argument is short, complete, and directly transferable to more complex algorithms like binary search or graph traversal correctness proofs. Its comparison with Selection Sort is a standard teaching pairing — both are Θ(n²) in the worst case and both sort in place, but only insertion sort adapts to already-sorted input.
:::quiz[Why does using A[j] > key, rather than A[j] >= key, matter?]
- It reduces the number of outer-loop iterations
- It changes the space complexity from O(1) to O(n)
- It preserves stability by not shifting equal elements past the key ✓
- It avoids integer overflow when comparing large numbers
Ask the tutor: How does binary insertion sort change the comparison count, and why doesn't it change the overall Θ(n²) bound?
Is insertion sort stable, and why does that matter?
Yes. Insertion sort is stable because its inner loop only shifts elements that are strictly greater than the key; elements equal to the key are never displaced, so the key is always inserted immediately after any equal elements already in the sorted prefix. Stability matters whenever you sort records by one field but want to preserve the relative order established by a previous sort on another field — for example, sorting a list of already-alphabetized names by department while keeping each department's names alphabetical. Many hybrid sorts (like Timsort) are specifically designed to be stable, and they rely on insertion sort's stability when using it as an internal subroutine for small runs.
How does insertion sort differ from selection sort if both are O(n²) and in-place?
Both algorithms maintain a growing sorted prefix, but they build it differently. Selection sort scans the entire unsorted suffix on every iteration to find the minimum element, so its running time is always Θ(n²), regardless of input order. Insertion sort instead takes the next unsorted element and shifts it left only as far as necessary, so its running time is data-dependent: Θ(n) on sorted input, Θ(n²) on reverse-sorted input. Insertion sort is also stable, while a naive selection sort implementation is typically not (swapping the minimum into place can jump it past equal elements). For nearly-sorted data, insertion sort is strictly preferable.
Can insertion sort be sped up with binary search for the insertion point?
Yes, partially. Using binary search to find the insertion index reduces the number of comparisons per element from O(i) to O(log i), which helps when comparisons are expensive (e.g., comparing long strings or complex objects). However, the shifting step still requires moving up to `i` elements in an array, which remains O(i) per insertion regardless of how the insertion point was found. So this variant, sometimes called "binary insertion sort," improves comparison count to O(n log n) total but keeps the overall time complexity at O(n²) due to the shifting cost. It is genuinely used in Timsort for exactly this comparison-cost benefit.
Why is insertion sort still used in real production code if it's O(n²)?
Asymptotic complexity describes behavior as n grows large, but for small n the constant factors dominate, and insertion sort has very small constants: no recursive call overhead, no auxiliary memory allocation, and excellent cache locality since it scans small contiguous regions repeatedly. Production hybrid sorts (Timsort, introsort, and similar) exploit this by using a fast O(n log n) algorithm to break the input into moderately sized pieces, then switching to insertion sort once pieces shrink below roughly 16–32 elements. At that scale, insertion sort's simplicity beats the overhead of further recursion, so the hybrid approach gets the best of both worlds.
What happens if you run insertion sort on an array that contains duplicate values?
Nothing breaks — insertion sort handles duplicates correctly and, as discussed, does so stably. When the key being inserted equals an element already in the sorted prefix, the inner while loop's strict `>` comparison causes the scan to stop at that equal element, and the key is inserted immediately to its right. This means the original left-to-right order of equal elements is preserved in the output, which is exactly the guarantee that "stable" sorting promises. No special-casing is needed in the pseudocode to handle duplicates correctly.
How does the loop invariant proof for insertion sort generalize to other algorithms?
The three-part structure — initialization, maintenance, termination — is a general template usable for any iterative algorithm, not just sorting. You identify a property that should hold at a specific point in every loop iteration, show it holds trivially before the loop starts, show that each iteration preserves it assuming it held before, and show that when the loop ends, the invariant implies the desired postcondition. This exact template is used to prove correctness of binary search, graph algorithms like breadth-first search, and numerical algorithms like Euclid's GCD computation, making insertion sort's proof a template worth memorizing.
Does insertion sort work on linked lists as well as arrays?
Yes, and in some ways it is more natural there: insertion into a linked list is O(1) once the correct position is found, because no shifting of subsequent elements is required — you just relink pointers. The search for the correct position is still O(i) in the worst case for a singly linked list (no random access, so no binary search is possible), so the overall worst-case time remains O(n²), but the algorithm avoids the array-shifting overhead entirely. This makes linked-list insertion sort a common teaching example for comparing array-based and pointer-based data structure tradeoffs.