Insertion Sort

Insertion sort builds a sorted array one element at a time — like sorting a hand of playing cards. Each new element is "inserted" into its correct position by shifting larger elements right to make room.

O(n²) worstO(n) bestO(n+k) adaptiveO(1) spaceStable ✓In-place

💡 The Core Idea

1Pick up the key

Take arr[i] — the next unsorted element. Remember its value. The sorted prefix is arr[0..i-1].

2Shift elements right

Scan left. Every sorted element larger than the key shifts one position right, opening a gap.

3Insert into the gap

When you find an element ≤ key (or reach the start), drop the key into the gap. Sorted prefix grows by one.

All Cases — Step by Step

😰 Worst Case — Reversed Array

Reversed: [5, 4, 3, 2, 1]O(n²)

[0]

[1]

[2]

[3]

[4]

Worst case: Reversed array [5, 4, 3, 2, 1]

Every new key is smaller than everything in the sorted prefix — it must travel all the way to the front. Maximum comparisons and shifts every pass.

💡 Reversed arrays cause O(n²) comparisons AND O(n²) shifts — every key must shift past the entire sorted prefix.

🚀 Best Case — Already Sorted

Sorted: [1, 2, 3, 4, 5]O(n) — true best case!

[0]

[1]

[2]

[3]

[4]

Best case: Already sorted [1, 2, 3, 4, 5]

Each key only needs ONE comparison — with the last element of the sorted prefix. It's always in the right place immediately. True O(n)!

💡 Unlike selection sort, insertion sort genuinely gets O(n) best case. Only n−1 comparisons, zero shifts.

⚡ Average Case — Nearly Sorted

Nearly Sorted: [1, 2, 4, 3, 5]O(n+k) adaptive

[0]

[1]

[2]

[3]

[4]

Nearly sorted: [1, 2, 4, 3, 5] — one inversion

Only elements 4 and 3 are out of order. Insertion sort detects this quickly — most keys need just 1 comparison.

💡 Insertion sort is optimal for nearly sorted data. k inversions → at most k shifts extra. This is its superpower.

🟰 Edge Case — All Equal

All Equal: [3, 3, 3, 3, 3]O(n) stable

[0]

[1]

[2]

[3]

[4]

All equal: [3, 3, 3, 3, 3]

Equal elements are never shifted — the comparison is strict (arr[j] > key, not ≥). Equal elements preserve their order, proving insertion sort is stable.

💡 Stability: equal elements keep their original relative order because we only shift on strictly greater. This makes insertion sort a stable sort.

Stability Explained

Insertion sort is stable — we only shift on strict >, never on equal. Equal elements always keep their original relative order.

Stability Demo — Sort by Grade

1AliceB

2BobA

3CarolB

4DaveA

Click 'Sort by Grade' to see insertion sort's stable behaviour — equal grades keep their original relative order.

Adaptivity — Insertion Sort's Superpower

✅ O(n + k) for k inversions

An inversionis any pair (i,j) where i < j but arr[i] > arr[j]. Insertion sort's shift count equals the exact number of inversions.

[1, 2, 3, 4, 5] → 0 inversions → O(n)

[1, 2, 4, 3, 5] → 1 inversion → O(n)

[2, 1, 4, 3, 5] → 2 inversions → O(n)

[5, 4, 3, 2, 1] → 10 inversions → O(n²)

🃏 The Card-Sorting Analogy

Imagine sorting a hand of cards. You pick up each new card and slide it left past larger cards until it reaches its spot. That's exactly insertion sort.

Hand: [5♠ 3♥ 7♦ 1♣ 4♠]

Pick 3♥ → slide past 5♠

Pick 7♦ → already right

Pick 1♣ → slide past all

Result: [1♣ 3♥ 4♠ 5♠ 7♦] ✓

💡 Why this matters in practice: Real-world data is often nearly sorted — log files with timestamps, live leaderboards, incremental updates. Insertion sort exploits this; selection sort and naive bubble sort (without optimization) cannot.

Shifts vs Swaps — An Important Distinction

❌ Swap-based (naïve) version

Some implementations use swaps like bubble sort. This does 3× as many writes per step.

j = i
while j > 0 and arr[j-1] > arr[j]:
arr[j], arr[j-1] = arr[j-1], arr[j]
j -= 1
# 3 writes per iteration (swap)

✅ Shift-based (correct) version

Save the key, shift elements right, then insert once. Only 1 write per shift + 1 final write.

key = arr[i] # save key once
j = i - 1
while j > 0 and arr[j] > key:
arr[j+1] = arr[j] # 1 write
j -= 1
arr[j+1] = key # 1 final write

Complexity Deep Dive

Case	Input	Comparisons	Shifts	Time	Why
😰 Worst	Reversed	n(n−1)/2	n(n−1)/2	O(n²)	Every key travels to index 0
📊 Average	Random	n(n−1)/4	n(n−1)/4	O(n²)	Each key shifts ~halfway on average
🚀 Best	Already sorted	n−1	0	O(n)	Each key needs only 1 comparison — already in place
🟰 Equal	All equal	n−1	0	O(n)	Strict > means no shifts; 1 comparison each pass
⚡ Nearly sorted	k inversions	n−1+k	k	O(n+k)	Adaptive: work proportional to disorder
—	Space (all cases)	—	—	O(1)	In-place — no extra array

✅ Key insight: Insertion sort's number of shifts equals exactly the number of inversions in the array. For nearly-sorted data with k inversions, it runs in O(n + k) — provably optimal for comparison-based sorting of nearly-sorted data.

Implementation

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):   # start from index 1
        key = arr[i]               # pick up the key element
        j = i - 1
        # shift elements greater than key one position right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]   # shift right
            j -= 1
        arr[j + 1] = key          # insert key into correct position
    return arr

# Test all cases
print(insertion_sort([64, 34, 25, 12]))  # Random    → [12, 25, 34, 64]
print(insertion_sort([1, 2, 3, 4]))      # Sorted    → [1, 2, 3, 4]   (O(n)!)
print(insertion_sort([4, 3, 2, 1]))      # Reversed  → [1, 2, 3, 4]   (O(n²))
print(insertion_sort([]))                # Empty     → []
print(insertion_sort([3, 3, 3]))         # Equal     → [3, 3, 3] (stable, O(n))

TypeScript

function insertionSort(arr: number[]): number[] {
  for (let i = 1; i < arr.length; i++) { // start from index 1
    const key = arr[i];                   // pick up the key
    let j = i - 1;
    // shift elements greater than key one step right
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];               // shift right (not a swap!)
      j--;
    }
    arr[j + 1] = key;                    // drop key into place
  }
  return arr;
}

// Edge cases
insertionSort([]);          // [] — 0 iterations
insertionSort([42]);        // [42] — single element, trivially sorted
insertionSort([3, 3, 3]);   // [3,3,3] — equal, 0 shifts, O(n) — stable ✓
insertionSort([5,4,3,2,1]); // reversed — O(n²) shifts, worst case
insertionSort([1,2,3,4,5]); // sorted — O(n) comparisons, 0 shifts ✓

Edge Cases to Handle

Empty array []

O(1)

Loop never runs (range(1, 0)). Return immediately. O(1).

Single element [x]

O(1)

Loop runs 0 times. The single element is trivially sorted.

Two elements [a, b]

O(1)

One comparison: if a > b, shift a right and place b. Otherwise do nothing.

All equal [x, x, x]

O(n)

Strict > means no shifts ever. n−1 comparisons, 0 shifts. Stable order preserved.

Already sorted

O(n)

Each key needs exactly 1 comparison. Zero shifts total. True O(n).

Reversed array

O(n²)

Every key shifts to index 0. n(n−1)/2 comparisons and shifts. Absolute worst case.

When to Use (and Not Use)

✅ Good for

• Nearly sorted data — provably optimal: O(n + k) for k inversions
• Online sorting — can sort as elements arrive one by one
• Small arrays (n < 20) — low overhead, cache-friendly, beats quicksort
• Stability required + small data — stable and simple
• As a subroutine — Tim Sort uses insertion sort for small runs (<64 elements)
• Teaching — intuitive card-sorting mental model

❌ Avoid when

• Large random datasets — O(n²) average is catastrophic at n=100,000+
• Worst-case guarantees — use Merge Sort or Heap Sort for O(n log n) worst
• Performance critical + large n — use Quick Sort or Tim Sort
• Reversed or highly shuffled data — every element travels maximum distance

Insertion Sort vs Others

Algorithm	Best	Average	Worst	Space	Stable	Notes
🃏 Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅	Adaptive; best for nearly sorted
🫧 Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅	Similar best case; more comparisons avg
🎯 Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌	No early exit; fewest swaps
🔀 Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅	Best stable sort for large n
⚡ Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌	Fastest in practice for random data
🐍 Tim Sort	O(n)	O(n log n)	O(n log n)	O(n)	✅	Uses insertion sort internally for runs

💡 Insertion sort is the best of the three O(n²) sorts for real-world use. It beats bubble sort on average (fewer comparisons and writes) and beats selection sort on best/nearly-sorted cases. Tim Sort — the algorithm powering Python and Java — uses insertion sort internally for subarrays smaller than 64 elements.