Insertion Sort

Insertion sort is the algorithm a human naturally uses to sort a hand of playing cards: pick up the cards one at a time, and slide each new card backward through the already-sorted portion of the hand until it sits in the right place. Algorithmically, it is O(n²) in the worst case but O(n) on already-sorted (or nearly sorted) input — making it adaptive. It is in-place (O(1) auxiliary), stable (equal elements keep their original relative order), and uses only one comparison and one shift per inversion. While useless as a general-purpose sort for large arrays, it is the base-case sort inside virtually every modern hybrid sort: Tim Sort, Intro Sort, std::sort, Java’s Arrays.sort — all switch to insertion sort once the subarray they are working on drops below ~16–32 elements, because for tiny n the small constants beat the asymptotic advantage of O(n log n) algorithms.

1. Intuition — Sorting a Hand of Playing Cards

You are dealt cards one at a time and want them sorted in your hand by rank.

• After picking up the first card, your hand is trivially sorted (one card).
• You pick up a second card. If it’s smaller than the card already in your hand, you slide it left — i.e., you insert it before the existing card. Now your hand is sorted (two cards).
• You pick up a third card. You compare it with the rightmost card in your sorted hand; if smaller, slide it left and compare again with the next card; keep sliding until you hit a card that is smaller-or-equal, or you reach the start of the hand. Drop the new card in that position.
• Continue for all n cards.

The invariant: after handling card k, the leftmost k cards of your hand are sorted. The new card you pick up “bubbles” backward into that sorted prefix, displacing larger cards to the right by one slot to make room.

Two things to notice:

1. The work per card depends on how out of place it is. If the new card is already larger than everything in your hand, you do one comparison and zero shifts. If it’s smaller than everything, you do k comparisons and k shifts. Average case: k/2 work per card. Total: O(n²). But on an already-sorted input, total: O(n).
2. No extra hand is needed. You shuffle the cards within the existing sorted prefix; no temporary storage. This is what “in-place” means.

2. Tiny Worked Example (n = 6)

Sort [5, 2, 4, 6, 1, 3] in ascending order. The pipe | separates the sorted prefix from the unsorted suffix. Each pass takes the first element of the unsorted suffix, calls it the key, and slides it backward into the sorted prefix.

Pass	Before	Key	Action	After
Initial	[5 | 2, 4, 6, 1, 3]	—	(single-element prefix is trivially sorted)	—
1 (i=1)	[5 | 2, 4, 6, 1, 3]	2	2 < 5: shift 5 right; place 2 at index 0	[2, 5 | 4, 6, 1, 3]
2 (i=2)	[2, 5 | 4, 6, 1, 3]	4	4 < 5: shift 5 right. 4 > 2: stop. Place 4 at index 1.	[2, 4, 5 | 6, 1, 3]
3 (i=3)	[2, 4, 5 | 6, 1, 3]	6	6 > 5: no shifts. Place 6 at index 3 (already there).	[2, 4, 5, 6 | 1, 3]
4 (i=4)	[2, 4, 5, 6 | 1, 3]	1	Slides past 6, 5, 4, 2 (4 shifts). Place 1 at index 0.	[1, 2, 4, 5, 6 | 3]
5 (i=5)	[1, 2, 4, 5, 6 | 3]	3	Slides past 6, 5, 4 (3 shifts). 3 > 2: stop. Place 3 at index 2.	[1, 2, 3, 4, 5, 6]

Done. Note pass 3 did one comparison and zero shifts (key was already in place), illustrating the algorithm’s adaptiveness — work scales with how out of place each element is.

The total number of shifts equals the number of inversions in the input (pairs (i, j) with i < j and arr[i] > arr[j]). For [5, 2, 4, 6, 1, 3]: inversions are (5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3) — that’s 9, matching the 0+1+1+0+4+3 = 9 shifts above.

3. Pseudocode

insertion_sort(arr):
    n := length(arr)
    for i from 1 to n - 1:
        key := arr[i]
        j   := i - 1
        # Slide elements > key one slot right, opening a hole for key.
        while j >= 0 and arr[j] > key:
            arr[j + 1] := arr[j]
            j := j - 1
        arr[j + 1] := key             # insert key into the hole

The while condition arr[j] > key (strict greater-than) is what makes the sort stable: when arr[j] == key, the loop stops and the new key is placed to the right of the equal element already in the prefix, preserving original input order. Switching to arr[j] >= key would still produce a sorted output but break stability.

4. Python Implementation

def insertion_sort(arr: list[int]) -> None:
    """Sort `arr` in place, ascending. Stable, in-place, adaptive."""
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # Slide larger elements right, leaving a hole for `key`.
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

A common code-golf alternative uses pairwise swaps instead of an explicit hole:

def insertion_sort_swaps(arr: list[int]) -> None:
    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
            j -= 1

The swap version does 3× as many memory writes per shift (the swap is three assignments — temp, copy, copy) compared to the “shift + final placement” version above. For interview code clarity either is fine; for performance prefer the shift version.

4.1 A Binary-Search Variant?

You might think: “the prefix arr[0..i-1] is sorted, so I can find the insertion position with binary search in O(log i) instead of linear scan.” This is binary insertion sort and reduces comparisons from O(n²) to O(n log n). But it does not reduce shifts. You still have to physically move elements right to open a hole, and that is O(n) per insertion. Total time stays O(n²). Useful only when comparisons are expensive (long strings, custom comparators) and shifts are cheap.

5. Complexity

5.1 Time

Worst case: O(n²). Reverse-sorted input. For each i, the key has to slide all the way to the front, doing i comparisons and i shifts. Total: Σ_{i=1}^{n-1} i = n(n-1)/2 = Θ(n²).

Best case: O(n). Already-sorted input. For each i, arr[j] > key is false immediately (the largest sorted-prefix element is arr[i-1] which is ≤ key), so the inner loop does zero iterations. Total: n - 1 = Θ(n) outer iterations, each doing O(1) work.

Average case: O(n²). A random permutation has expected n(n-1)/4 inversions, and each inversion costs one shift. So expected time is Θ(n²).

Why insertion sort can’t beat the comparison-sort lower bound Ω(n log n) in the worst case. Any comparison-based sort can be modeled as a decision tree: each internal node is one comparison, each leaf is a permutation of the input. There are n! permutations, so the tree’s worst-case path (= worst-case comparison count) is at least ⌈log₂(n!)⌉ = Θ(n log n) (Stirling). Insertion sort hits Θ(n²) worst-case, which is consistent with — and worse than — the lower bound. The lower bound says no comparison sort can be better than Θ(n log n), not that all of them must achieve it.

5.2 Adaptiveness — The “Nearly Sorted” Bonus

A sort is adaptive if it runs faster when the input is already partially sorted. Insertion sort’s running time is Θ(n + I) where I is the number of inversions in the input. Concretely:

• Already sorted: I = 0, time Θ(n).
• One element out of place: I ≤ n, time Θ(n).
• k swaps away from sorted: I ≤ k · n, time O(n + kn) = O(kn).
• Random: I = Θ(n²), time Θ(n²).

This is why insertion sort is excellent for maintaining a sorted list as elements arrive in nearly-correct order, and why it is the inner loop of Tim Sort (which exploits “natural runs” of pre-sorted data and uses insertion sort to extend short runs to a minimum length).

5.3 Space

• Auxiliary: O(1) — just key, i, j.
• Stack: O(1) — no recursion.
• Truly in-place.

6. Stability

Insertion sort is stable when implemented with arr[j] > key (strict >). When the inner loop encounters arr[j] == key, it exits, and key is placed at j + 1 — to the right of the equal element already in the prefix. So elements that were equal in the input stay in their input-order in the output.

If the predicate were arr[j] >= key, the loop would slide an equal element right, putting key to the left of it, reversing their relative order. The output would still be sorted, but stability would be lost. Always use strict > if stability matters.

7. Where Insertion Sort Lives in Production — The Base Case of Hybrid Sorts

Insertion sort’s O(n²) complexity rules it out as a general sort. But for small n, the constants matter more than the exponent. For n ≤ 16 or so, insertion sort is empirically faster than Quicksort or Merge Sort, because:

• The inner loop is a single comparison and a single shift — fewer instructions per iteration than quicksort’s partition or merge sort’s merge.
• No recursion overhead (function call, stack frame setup).
• Linear memory access pattern → great cache behavior.
• No work to set up auxiliary buffers, pivots, or heaps.

So almost every modern sort hybrid uses insertion sort as the base case for tiny subarrays.

7.1 Tim Sort (Python’s sorted(), Java’s Arrays.sort for Object[])

Tim Peters’s Tim Sort design notes define a parameter MIN_RUN, typically computed at runtime in the range [32, 64] based on n. Any natural run shorter than MIN_RUN is extended to MIN_RUN by binary insertion sort on the tail. This means insertion sort is the inner sort for every short run that Tim sort produces — without it, Tim sort wouldn’t have the right run-length distribution for its merge strategy. See Tim Sort for the full algorithm.

7.2 Intro Sort (C++ std::sort, .NET Array.Sort, Rust sort_unstable)

Musser’s introsort (1997) starts with Quicksort, falls back to Heap Sort when recursion gets too deep, and switches to insertion sort for subarrays smaller than ~16 elements. The exact threshold is implementation-dependent: libstdc++ uses 16, MSVC uses 32, and Rust’s pattern-defeating quicksort pdqsort uses 24. See Intro Sort.

7.3 Java’s Arrays.sort for Primitives

For primitive types (int[], long[], etc.), Java uses Dual-Pivot Quicksort (Yaroslavskiy 2009) with insertion sort as the base case for arrays of length ≤ 47 (INSERTION_SORT_THRESHOLD). For arrays of length ≤ 286 (“small” by Java’s threshold), an even larger insertion-sort variant is used.

7.4 Why This Matters For Interviews

If an interviewer asks “which sort is fastest in practice?” and you answer “Quicksort,” you’re partially right — but the complete answer recognizes that production sorts are always hybrids, and insertion sort is part of the recipe for nearly all of them. Mentioning the hybrid nature signals deeper familiarity than naming a single textbook algorithm.

8. Variants

8.1 Binary Insertion Sort

Use binary search to locate the insertion position in the sorted prefix. Reduces comparisons from O(n²) to O(n log n), but shifts remain O(n²), so total time stays quadratic. Useful when comparisons are very expensive. Tim sort uses this internally because comparisons of arbitrary Python objects (or Java Comparables) can be slow.

8.2 Shell Sort

Shell sort (Donald Shell 1959) is a generalization of insertion sort that does multiple passes with progressively smaller “gaps” — first sort elements that are h apart for some large h, then h/2, …, finally h = 1 (which is just regular insertion sort). The intermediate gap-sorted passes move elements closer to their final positions efficiently, so the final h = 1 pass has very few inversions left to fix. Shell sort runs in O(n^(4/3)) to O(n log² n) depending on the gap sequence (Pratt’s O(n log² n) is the best known for arbitrary input). It was the dominant in-place sort before quicksort took over and is still used in some embedded systems.

8.3 Library Sort (Bender et al. 2006)

A randomized variant that leaves gaps between elements in the sorted prefix, so that insertions only require shifting O(log n) elements on average instead of O(n). Achieves O(n log n) expected time with high probability. Theoretically interesting but not used in production.

9. Pitfalls

9.1 Strict vs Non-Strict Comparison Breaks Stability

Using arr[j] >= key instead of arr[j] > key produces a sorted output but reverses the relative order of equal elements. Easy mistake; silent bug.

9.2 Off-by-One on the Final Placement

After the inner loop, j points to the index just before where key should go (or -1 if the key belongs at the start). The final assignment is arr[j + 1] = key, not arr[j] = key. Getting this wrong overwrites a valid element.

9.3 Forgetting That Index 0 is Already “Sorted”

The outer loop starts at i = 1, not i = 0. A single element is trivially a sorted array. Starting at 0 is harmless (the inner loop immediately exits) but technically unnecessary.

9.4 Choosing Insertion Sort for Large n

Insertion sort’s O(n²) is brutal at scale. Sorting a 1-million element random array with insertion sort would take ~10^12 operations — about 17 minutes on a modern CPU. The same task takes ~milliseconds with Quicksort or Tim Sort. Use insertion sort only when n ≤ ~50, or as a base case inside a hybrid.

9.5 Confusing With Selection Sort or Bubble Sort

These three are the classic O(n²) sorts often introduced together. They differ:

• Insertion sort: for each new element, slide it backward into the sorted prefix. Adaptive (O(n) on sorted input). Stable.
• Selection sort: for each position, scan the remaining suffix to find the minimum, swap into place. Always Θ(n²). Not adaptive. Not stable in the standard formulation.
• Bubble sort: repeatedly pass through the array, swapping adjacent out-of-order pairs. O(n²) worst, O(n) best (with early-exit flag). Stable. Used essentially nowhere in practice.

Insertion sort is the only one of the three with practical use today.

10. Diagram — The Sliding Window

flowchart LR
    subgraph Before["Before pass i (i=4)"]
        B0["arr[0]=2"]:::sorted
        B1["arr[1]=4"]:::sorted
        B2["arr[2]=5"]:::sorted
        B3["arr[3]=6"]:::sorted
        B4["arr[4]=1"]:::key
        B5["arr[5]=3"]:::unsorted
    end
    subgraph Slide["Inner loop sliding the key (=1) leftward"]
        S0["1"]:::key -.-> S1["..."] -.-> S2["compare 6,5,4,2"] -.-> S3["place 1 at index 0"]
    end
    subgraph After["After pass i"]
        A0["arr[0]=1"]:::sorted
        A1["arr[1]=2"]:::sorted
        A2["arr[2]=4"]:::sorted
        A3["arr[3]=5"]:::sorted
        A4["arr[4]=6"]:::sorted
        A5["arr[5]=3"]:::unsorted
    end
    Before --> Slide --> After
    classDef sorted fill:#cfc,stroke:#333
    classDef key fill:#fdd,stroke:#900,stroke-width:2px
    classDef unsorted fill:#eee,stroke:#666,stroke-dasharray: 3 3

What this diagram shows. The state of the array around one iteration of the outer loop. The green prefix (arr[0..3]) is the already-sorted region built by previous passes; the dashed gray suffix (arr[5..]) is yet to be processed. The red highlighted cell is the key — the next element to be inserted into the sorted prefix. The middle subgraph traces the inner loop comparing the key against successive prefix elements (right-to-left), shifting each larger element rightward until the key finds its sorted position. The post-state shows the prefix has grown by one and the key is now in its correct relative location among the sorted elements. Crucially, all motion happens within the original array — no auxiliary buffer is used — which is why insertion sort is in-place.

11. Common Interview Problems

Problem	Insertion Sort Connection
”Sort an almost-sorted array (each element at most k away from its correct position)“	Insertion sort runs in O(nk). Optimal answer if k is small.
”Sort a small array (n < 50) where simplicity matters”	Insertion sort is concise, in-place, stable, and competitive.
”Insert a value into a sorted array, maintaining sort”	Single iteration of insertion sort’s inner loop — O(n).
”Sort a singly linked list, in place, with O(1) extra space”	Insertion sort works on linked lists with O(n²) time but O(1) aux. (Linked-list merge sort is O(n log n) but uses recursion stack.)
”Why does the standard library switch to insertion sort for small subarrays?”	Constants beat asymptotics at small n; cache-friendly; no recursion overhead.

12. Open Questions

• What is the exact crossover point (in n) where insertion sort becomes slower than Merge Sort or Quicksort on modern CPUs? Folklore says ~16; depends heavily on CPU cache size, branch predictor, and key type.
• Why do different production hybrids choose different insertion-sort thresholds (16 vs 32 vs 47)? Empirical tuning on different benchmark suites?
• Could a “skip-list-style” gapped insertion sort (Library Sort) be made fast enough in practice to displace classical insertion sort as the small-n base case? Probably not, but worth checking the recent literature.

13. See Also

• Tim Sort — uses insertion sort to extend short natural runs
• Intro Sort — uses insertion sort for subarrays under threshold
• Merge Sort — O(n log n) and stable; preferred for large n
• Quicksort — O(n log n) average; preferred for in-place large-n sorting
• Heap Sort — O(n log n) worst-case in-place; preferred for guarantees
• Counting Sort — beats insertion sort when keys have small bounded range
• Big-O Notation
• SWE Interview Preparation MOC