← SciSim / Computer Science

Insertion Sort

⚙️ Tier: HSC / Early Undergraduate
📊 Section 1 — Interactive Simulation
Step 0 / 0
Press Play to run Insertion Sort step by step.
0
Comparisons
0
Shifts
0
Step
20
Input n
0
Key #
Key (being inserted)
Comparing
Shifting right
Sorted region
Unsorted
Pseudocode
1procedure InsertionSort(A[0..n-1]): 2 for i ← 1 to n-1 do 3 key ← A[i] // element to insert 4 j ← i - 1 5 while j ≥ 0 and A[j] > key do 6 A[j+1] ← A[j] // shift right 7 j ← j - 1 8 A[j+1] ← key // place key 9 return A
Input Size (n)
n = 20
Preset
Custom Input
Actions
Display Options
Index Labels
Value Labels
Key Pointer
Sorted Region Line
📖 Section 2 — The Idea, Step by Step

Pick up a hand of playing cards one at a time. Each new card you grab, you slide left along the cards you're already holding until it sits in the right spot, then you grab the next one. The cards in your hand stay sorted the whole time, and the pile on the table shrinks. That is the entire algorithm — insertion sort is just "sort your hand as you deal."

Let's name the pieces. The sorted region is the part of the array on the left that's already in order (the cards in your hand). The key is the next item you pull from the unsorted pile. To place the key, you compare it to the sorted items from right to left; every item bigger than the key shifts one slot to the right to open a gap, and the key drops into that gap. The simplest way to count the work is: each key does a few comparisons, plus one shift for every larger item it has to pass. If a hand of 5 cards is already in order, each new card just gets one quick peek and stays put — that's only $4$ comparisons and $0$ shifts. Easy hands are cheap; messy hands are dear.

To be precise, for an array of size $n$ the number of comparisons runs from a best case of $n-1$ (already sorted) up to a worst case of $\frac{n(n-1)}{2}$ (reverse sorted). The real cost driver is the inversion count $I$ — the number of out-of-order pairs in the input. Insertion sort performs exactly one shift per inversion, so total shifts $= I$ and the running time is $T = \mathcal{O}(n + I)$. That single formula explains everything: a nearly-sorted array has $I = \mathcal{O}(n)$ inversions, so the sort finishes in near-linear time, while a reverse-sorted array has the maximum $I = \frac{n(n-1)}{2}$ and the sort degrades to $\mathcal{O}(n^2)$. On the sliders above, Input Size sets $n$ and the Preset menu sets how scrambled the input is; the Comparisons and Shifts cards count the work live.

Try this in the sim above:

1. Set the Preset to Already sorted and step through — watch Shifts stay at $0$ while Comparisons climb only to $n-1$. That's the $\mathcal{O}(n)$ best case.

2. Switch to Reverse sorted — every key has to slide all the way left, and Shifts climbs to the maximum $\frac{n(n-1)}{2}$. That's the $\mathcal{O}(n^2)$ worst case.

3. Pick Nearly sorted and compare the totals to a random array of the same $n$ — almost no shifts, because there are only a handful of inversions to fix. That's why Timsort hunts for nearly-sorted runs.

📐 Section 3 — Algorithm Analysis & Derivation

Insertion Sort — Origin & History

Insertion Sort models the way a card player sorts a hand of cards: pick up each card and slide it into the correct position among the already-sorted cards in hand. It is one of the most practically useful simple sorting algorithms, forming the basis of Timsort (Python, Java's Arrays.sort for small arrays) and Shell Sort. For nearly-sorted arrays and small n, it is often the fastest algorithm in practice due to its minimal overhead and excellent cache behavior.

Symbol Table

SymbolMeaningRange
\(n\)Input array size\(\mathbb{Z}^+\)
\(T(n)\)Number of comparisons\([n-1,\ \frac{n(n-1)}{2}]\)
\(I\)Number of inversions in input\([0,\ \frac{n(n-1)}{2}]\)
\(\text{key}\)Current element being inserted\(A[i]\)
\(i\)Outer loop: current key index\(1 \leq i \leq n-1\)
\(j\)Inner loop: scan back position\(-1 \leq j \leq i-1\)
\(S(n)\)Number of shifts = number of inversions\([0,\ \frac{n(n-1)}{2}]\)

Step-by-Step Complexity Derivation

Step 1 — Inversions as the true cost driver

Each shift in the inner loop corrects exactly one inversion. Therefore the total number of shifts (and comparisons within 1) equals the number of inversions \(I\) in the input permutation:

$$\text{Shifts} = I, \quad \text{Comparisons} \in [I, I + (n-1)]$$

Step 2 — Best case (sorted input: I = 0)

If the array is sorted, every key is already in place. The inner while-loop exits immediately. Only \(n-1\) comparisons are made (one per outer loop iteration):

$$B(n) = n-1 \implies \mathcal{O}(n)$$

Step 3 — Worst case (reverse-sorted: maximum inversions)

Reverse-sorted input has \(\binom{n}{2} = \frac{n(n-1)}{2}\) inversions. Key at position \(i\) must shift all \(i\) elements before it:

$$W(n) = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \Theta(n^2)$$

Step 4 — Average case (random permutation)

Expected number of inversions in a random permutation of \(n\) elements is \(\binom{n}{2}/2 = \frac{n(n-1)}{4}\):

$$A(n) = \frac{n(n-1)}{4} = \Theta(n^2)$$

Step 5 — Input-sensitive complexity

Insertion Sort is input-sensitive — its runtime depends on the degree of sortedness. For arrays with \(\mathcal{O}(n)\) inversions (nearly sorted), it runs in \(\mathcal{O}(n)\). This is the formal reason Timsort uses Insertion Sort on small nearly-sorted runs.

$$T = \mathcal{O}(n + I) \quad \text{where } I = \text{number of inversions}$$

Step 6 — Space and stability

$$\text{Space} = \mathcal{O}(1) \text{ auxiliary}$$

Insertion Sort is stable: the condition A[j] > key (strict >) ensures equal elements are not shifted, preserving their relative order.

Step 7 — Binary Insertion Sort variant

Use binary search to find the insertion position in O(log i) comparisons per key, reducing total comparisons to \(\mathcal{O}(n \log n)\). However, shifts remain \(\mathcal{O}(n^2)\) in the worst case — so overall complexity stays \(\mathcal{O}(n^2)\) unless combined with a linked structure.

Worked Trace Example (n = 6)

Array: [5, 3, 8, 1, 9, 2]

i=1, key=3: Compare 3 vs 5 → shift 5 right → [5,5,8,1,9,2] → insert 3 → [3,5,8,1,9,2]. Shifts:1.

i=2, key=8: Compare 8 vs 5 → no shift (8>5). Insert in place → [3,5,8,1,9,2]. Shifts:0.

i=3, key=1: Compare vs 8→shift; vs 5→shift; vs 3→shift → [3,5,8,8,9,2]→[3,5,5,8,9,2]→[3,3,5,8,9,2]. Insert → [1,3,5,8,9,2]. Shifts:3.

i=4, key=9: Compare vs 8 → no shift. → [1,3,5,8,9,2]. Shifts:0.

i=5, key=2: Compare vs 9,8,5,3,1 → shift 4 elements → insert → [1,2,3,5,8,9]. Shifts:4.

Final: [1,2,3,5,8,9]. Total comparisons: 11. Total shifts: 8 (equal to the 8 inversions in the input).

References

[1] Cormen et al. — CLRS 4th ed. 2022, Ch. 2 "Getting Started" (Insertion Sort is the Chapter 2 example)
[2] Sedgewick & Wayne — Algorithms 4th ed., §2.1 "Elementary Sorts"
[3] Knuth — TAOCP Vol. 3, §5.2.1 "Sorting by Insertion"
❓ Section 4 — FAQ
⚙️ ConceptualWhat is the loop invariant for Insertion Sort?▼
At the start of each iteration of the outer for loop, the subarray A[0..i-1] consists of the elements originally in those positions but in sorted order. This is the classic CLRS loop invariant. Initialization: A[0..0] is trivially sorted. Maintenance: inserting key into its correct position among A[0..i-1] keeps the subarray sorted. Termination: when i=n, A[0..n-1] is sorted. This three-part proof is the standard way to formally verify sorting algorithm correctness.
Key takeaway: The loop invariant "A[0..i-1] is sorted" is the formal correctness proof — CLRS uses Insertion Sort as its canonical example of loop invariant reasoning.
🌍 AppliedWhere does Insertion Sort appear in production systems?▼
Insertion Sort is the foundation of Timsort — the default sorting algorithm in Python (sort(), sorted()), Java (Arrays.sort() for objects), and Android. Timsort uses Insertion Sort for small runs (n ≤ 64) within a merge sort framework. It also appears in database systems for maintaining sorted indexes during small batch inserts. The GCC standard library uses Insertion Sort as the base case of Introsort (hybrid quicksort). Its near-O(n) performance on nearly-sorted data makes it ideal for maintaining sorted order during streaming data ingestion.
Key takeaway: Every time you call Python's sorted() on a list, Insertion Sort runs on the small chunks — it's in production in billions of devices.
🔬 SimulationWhat is the yellow "Key" marker in the simulation showing?▼
The yellow cell marks the "key" — the element currently being extracted and inserted into the sorted portion. Watch how the blue cells to its left are compared against the key. When a blue cell's value exceeds the key, it shifts one position right (shown in orange). The key is conceptually "lifted out" and held in a temporary variable while the sorted elements shift to make room. The green region grows from left to right as each key finds its insertion point.
Key takeaway: The yellow key "slides left" through the sorted region until it finds its correct position — this is exactly how you sort cards in your hand.
💡 Non-ObviousWhy is Insertion Sort faster than Merge Sort and Quick Sort for small n?▼
Asymptotically, Merge Sort is O(n log n) vs Insertion Sort's O(n²). But for small n (typically n ≤ 16–32), Insertion Sort wins due to: (1) zero function call overhead (no recursion), (2) sequential memory access pattern (excellent cache locality), (3) tiny constant factor in the inner loop. Profiling shows Insertion Sort is faster than Merge Sort for n ≤ ~30 in practice. This is why virtually all production sorting implementations switch to Insertion Sort for small subproblems. The crossover point is hardware-dependent.
Key takeaway: Big-O ignores constant factors — for n ≤ ~30, Insertion Sort's constants beat Merge Sort's recursion overhead every time.
📐 ComplexityWhat does it mean that Insertion Sort is O(n + I) where I is the inversion count?▼
Insertion Sort performs exactly one shift per inversion — each time A[j] > key, one inversion is eliminated. So total shifts = total inversions = I. Adding the n-1 comparisons that don't result in shifts: T(n,I) = n-1 + I = O(n + I). For sorted input: I=0, T = O(n). For reverse-sorted: I = n(n-1)/2, T = O(n²). For "almost sorted" with I = O(n): T = O(n) — linear! This makes Insertion Sort the theoretically optimal algorithm for inputs with O(n) inversions.
Key takeaway: T = O(n + I) — Insertion Sort's runtime adapts to input order; it's not just O(n²), it's O(inversion count).
🎓 DeepHow does Shell Sort extend Insertion Sort, and why does it help?▼
Shell Sort (D.L. Shell, 1959) runs Insertion Sort multiple times with decreasing gap sequences. First, elements gap positions apart are sorted; the gap decreases each pass until gap=1 (which is regular Insertion Sort). Large-gap passes move elements close to their final positions quickly, reducing the inversion count for subsequent passes. The key insight: Insertion Sort on a nearly-sorted array is O(n), so if prior passes make it nearly sorted, total work is much less than O(n²). With Knuth's gap sequence (3^k - 1)/2, complexity is O(n^{3/2}); with Sedgewick's sequence, it approaches O(n^{4/3}).
Key takeaway: Shell Sort = Insertion Sort + pre-sorting with large gaps; it proves that Insertion Sort's O(n + I) property can be exploited to beat O(n²).

References

CLRS 4th ed. Ch. 2 (canonical Insertion Sort reference) · Visualgo — visualgo.net · MIT 6.006 OCW Lecture 3
⚠️ Section 5 — Misconceptions & Common Errors

Sub-block A: Conceptual Misconceptions

❌ Misconception: "Insertion Sort's best case O(n) is a fluke — it's still essentially O(n²)."
✅ Correction: The O(n) best case is not a fluke — it is a rigorous consequence of the O(n + I) analysis. For any input with O(n) inversions (e.g., sorted array, nearly-sorted array with k random swaps where k = O(1)), Insertion Sort genuinely runs in O(n) time. This property is exploited by Timsort: it detects sorted/nearly-sorted runs and processes them with Insertion Sort in linear time, then merges the runs.
📖 CLRS 4th ed., Ch. 2.1; Timsort paper — Peters 2002
❌ Misconception: "Insertion Sort makes n² comparisons, same as Bubble Sort and Selection Sort."
✅ Correction: This is true in the worst case, but NOT in the average or best case. Insertion Sort has fewer average-case comparisons than Bubble Sort because it stops the inner scan as soon as the correct position is found — it doesn't scan the full remaining array. Bubble Sort with early exit also terminates early, but per-pass, not per-element. Insertion Sort's inner while loop performs exactly I+n-1 comparisons total where I is the inversion count.
📖 Sedgewick & Wayne — Algorithms 4th ed., §2.1
❌ Misconception: "Insertion Sort is stable only if you implement it carefully."
✅ Correction: The standard implementation using strict > (not ≥) in the while condition is unconditionally stable. The inner loop stops when A[j] ≤ key, so equal elements are never shifted past each other. Using ≥ instead of > breaks stability. This is an important detail: the standard textbook algorithm as written in CLRS is stable by definition, not by accident.
📖 Knuth TAOCP Vol. 3, §5.2.1

Sub-block B: Implementation Errors

❌ Error: Starting outer loop at i=0: for i in range(n).
✅ Correct: Start at i=1. A[0..0] is already trivially sorted — there's nothing to compare the first element against. Starting at 0 causes the inner while loop to attempt j = i-1 = -1, requiring an extra bounds check on every iteration or an array-out-of-bounds error.
🔍 Students misread "for i=0 to n-1" from Selection Sort and apply the same range to Insertion Sort.
❌ Error: Using A[j] >= key instead of A[j] > key in the while condition.
✅ Correct: The condition must be strict >. Using ≥ makes the sort unstable by shifting equal elements, and also performs one extra unnecessary comparison at the correct insertion point. For the standard stable sort behavior used in production (Timsort requires stability), always use strict greater-than.
🔍 Students write ≥ thinking it makes the "stop condition" more conservative, unaware it breaks stability.
❌ Error: Incrementing j after the loop: A[j+1] = key — confusing j's final value.
✅ Correct: After the while loop exits, j is one position before the insertion point (j is either -1 or the index of the first element ≤ key). So the key goes at A[j+1]. A common error is writing A[j] = key (off by one) or incrementing j before placing the key, shifting it by an extra position and corrupting the sorted order.
🔍 Off-by-one errors in loop variable final values are among the most common bugs in sorting implementations.

References

CLRS 4th ed. Ch. 2 · Sedgewick & Wayne — Algorithms 4th ed. · Skiena — Algorithm Design Manual 3rd ed.