Insertion sort

The problem it solves

Not every sorting job is a million random records. A constant stream of small arrays; data that is already almost in order; a sort that must run in-place, stably, with code you could write on a napkin — this is insertion sort’s territory, and it is bigger than the O(n²) label suggests. Production sorts (TimSort, introsort, pdqsort) all switch to insertion sort for small ranges, because below a few dozen elements its tiny constants beat every clever algorithm’s overhead. If you have ever called a standard library sort, insertion sort ran.

Its second domain is nearly sorted data — a log that’s ordered except for a few late arrivals, a list maintained sorted as items trickle in. There, insertion sort is not a slow algorithm with a nice constant; it is genuinely O(n + d) where d is the number of inversions, which for nearly-sorted input approaches linear.

The intuition — and where it breaks down

Sorting a hand of cards. You pick up the next card and slide it leftward past every card bigger than it, into its slot. The cards already in your hand are always ordered; each new card only has to find its place among them. Nobody teaches you this — it is what hands do — which is why insertion sort is the one algorithm most people invent independently.

Two places the analogy quietly lies. First, sliding a card between two others is free with paper; in an array, making a gap means shifting every larger element one slot right, one write each — the shifts, not the comparisons, are where the quadratic cost lives. Second, your hand finds the slot by glancing; the algorithm walks one comparison at a time from the right, and stops at the first element not bigger than the key — that strictness (>, never >=) is invisible with cards but is exactly what makes the sort stable.

Loading…

A walkthrough you can check

Sort [5, 2, 4, 6, 1].

1. 5 alone is a sorted prefix.
2. Key 2: walk left past 5 (one shift), place at 0 → [2, 5, 4, 6, 1].
3. Key 4: past 5 (one shift), stop at 2 → [2, 4, 5, 6, 1].
4. Key 6: 5 is not bigger — zero shifts, it was already in place. This is the adaptive case, and on nearly-sorted input it is almost every case.
5. Key 1: past 6, 5, 4, 2 — four shifts → [1, 2, 4, 5, 6].

Total: seven shifts, and each one canceled exactly one inversion (a pair out of order). That equivalence — shifts = inversions — is the precise version of “insertion sort is fast on nearly-sorted data”, and the prediction prompt in the visualization asks you to count the shifts before they happen: it’s just “how many sorted-prefix values exceed the key”.

The invariant

After processing index i, a[0..i] is sorted — not finished, sorted-so-far: those elements may still shift right to admit later keys. Compare selection sort’s stronger claim (prefix elements are in final position) and you have the essential contrast between the two: insertion sort’s weak invariant is what lets it exploit existing order; selection sort’s strong invariant is what forces it to scan everything every time.

The inner loop’s own invariant is the stability proof: the walk stops at the first element ≤ key, so among equals the newcomer lands to the right of the incumbents — original order preserved. Change one comparison to >= and equal elements swap places silently.

Complexity, derived

Comparisons + shifts, counted honestly. Worst case (reversed input): key i walks past all i predecessors, Σi = n(n−1)/2 — quadratic, and the reversed preset’s counters show it. Best case (sorted): each key makes one comparison, zero shifts — n−1 comparisons total, linear, visible in the sorted preset. The general truth interpolates: exactly d shifts for d inversions, plus at most n−1 “stop” comparisons. Random input has ~n²/4 inversions on average, hence the quadratic average case.

Space O(1), and — a point for the systems-minded — the access pattern is a tight rightward-moving window, which is as cache-friendly as algorithms get. That, plus no recursion and no bookkeeping, is why it wins small ranges against O(n log n) rivals.

What people get wrong

Swapping instead of shifting. A version that repeatedly swaps the key leftward is correct but does ~2× the writes: each swap is two writes where a shift is one, and the key gets rewritten at every position instead of once at the end. Interviewers notice.

Starting the outer loop at 0. Index 0 is already a sorted prefix of one; starting there wastes a pass and, in some formulations, reads a[-1].

Writing the key back at j instead of j + 1. After the walk, j points at the first non-greater element (or −1); the slot is one to its right. This off-by-one produces arrays that are subtly wrong only when shifts actually occurred — property tests catch it, eyeballs often don’t.

Believing “quadratic” ends the conversation. “When would you use insertion sort?” has real answers — small n, nearly-sorted, online insertion, the base case of every hybrid sort — and “never, it’s O(n²)” is the wrong one.

Implementation notes across languages

In Python, the idiomatic online form is bisect.insort, which binary-searches the slot and then shifts — fewer comparisons, same shift cost, a nice talking point about which factor actually dominates (the shifts; binary insertion sort is still O(n²)). In Java and C++, the shift is System.arraycopy / std::move_backward territory when performance matters — turning n single writes into one block move. In JavaScript, beware splice for the insertion: it shifts internally and allocates, giving you the quadratic twice. The standard-library connection is worth repeating: TimSort’s minrun insertion phase means this “beginner” algorithm executes inside every Python and modern JS sort call.