Insertion Sort

Sorting Cards as You're Dealt Them

You're playing a card game and the dealer slides cards to you one at a time. You don't wait for all cards to arrive before organizing — you sort as you go. Each new card arrives and you slide it into its correct position among the cards already in your hand.

When you get 7, your hand is: [7] You get 3 — slide it left of 7: [3, 7] You get 9 — it's bigger than 7, stays right: [3, 7, 9] You get 5 — slide it between 3 and 7: [3, 5, 7, 9] You get 1 — slide all the way left: [1, 3, 5, 7, 9]

At every moment, the cards in your hand are sorted. When the next card arrives, you insert it into the right spot. This is insertion sort — and it's exactly how most people naturally sort things.

How Insertion Sort Works

The algorithm maintains two logical regions:

[  sorted portion  |  unsorted portion  ]

• Start: sorted portion = first element alone, unsorted = everything else
• Each step: take the first element of the unsorted portion (the "key")
• Slide it leftward through the sorted portion until it finds its correct position
• Repeat until no unsorted portion remains

Visual step-by-step on [12, 11, 13, 5, 6]:

Start:    [12 | 11, 13, 5, 6]   ← 12 is trivially sorted

Step 1:   key = 11
          11 < 12 → shift 12 right: [_, 12, 13, 5, 6]
          Insert 11 at position 0:  [11, 12 | 13, 5, 6]

Step 2:   key = 13
          13 > 12 → no shift needed
          Result: [11, 12, 13 | 5, 6]

Step 3:   key = 5
          5 < 13 → shift 13 right: [11, 12, _, 13, 6]
          5 < 12 → shift 12 right: [11, _, 12, 13, 6]
          5 < 11 → shift 11 right: [_, 11, 12, 13, 6]
          Insert 5 at position 0:  [5, 11, 12, 13 | 6]

Step 4:   key = 6
          6 < 13 → shift: [5, 11, 12, _, 13]
          6 < 12 → shift: [5, 11, _, 12, 13]
          6 < 11 → shift: [5, _, 11, 12, 13]
          6 > 5  → stop, insert: [5, 6, 11, 12, 13]

Final:    [5, 6, 11, 12, 13]

Full Implementation with Step Printing

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]          # the element to be inserted
        j = i - 1             # start comparing from element just before key

        # Shift elements that are greater than key one position to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]   # shift right (not a swap — more efficient)
            j -= 1

        arr[j + 1] = key          # insert key into its correct position
        print(f"After inserting {key}: {arr}")

    return arr

arr = [12, 11, 13, 5, 6]
result = insertion_sort(arr)
print(f"Sorted: {result}")

Output:

After inserting 11: [11, 12, 13, 5, 6]
After inserting 13: [11, 12, 13, 5, 6]
After inserting 5:  [5, 11, 12, 13, 6]
After inserting 6:  [5, 6, 11, 12, 13]
Sorted: [5, 6, 11, 12, 13]

Notice: Insertion sort uses shifts, not swaps. When inserting key, elements are moved one position right. This is more efficient than swapping — it touches each element once instead of multiple times.

Complexity Analysis

Best case trace on [1, 2, 3, 4, 5]:

key = 2: arr[0]=1 < 2 → while loop doesn't execute → 1 comparison
key = 3: arr[1]=2 < 3 → while loop doesn't execute → 1 comparison
key = 4: arr[2]=3 < 4 → while loop doesn't execute → 1 comparison
key = 5: arr[3]=4 < 5 → while loop doesn't execute → 1 comparison
Total: n-1 comparisons = O(n)

This O(n) best case is why insertion sort is used inside more complex algorithms for small or nearly-sorted chunks.

Why Insertion Sort Wins for Small Arrays

Even though insertion sort is O(n²) in theory, it outperforms merge sort and quicksort for small arrays in practice. Here's why:

1. Cache efficiency Insertion sort accesses memory sequentially — it walks left from the current position. Modern CPUs cache nearby memory, so sequential access is extremely fast. Merge sort and quicksort make scattered memory accesses.

2. Low overhead Complex algorithms have overhead: function calls, pointer arithmetic, stack management. For 10 elements, this overhead often exceeds the cost of the O(n²) comparisons.

3. In-place operation No auxiliary memory allocation needed. For small arrays, memory allocation itself has measurable cost.

Benchmark intuition (approximate):

The crossover point is typically around n = 10–20 elements.

Insertion Sort vs. Bubble Sort

Both are O(n²), but insertion sort is meaningfully better:

Online algorithm: Insertion sort can sort a list as it receives elements, without needing the full list first. Bubble sort cannot.

On average, insertion sort does half as many comparisons as bubble sort. For random data with n=1000:

• Bubble sort: ~500,000 comparisons
• Insertion sort: ~250,000 comparisons

Real-World Use: Python's Timsort

Python's built-in sort() and sorted() use Timsort — a hybrid algorithm invented by Tim Peters in 2002. Timsort splits arrays into small chunks (called "runs") of typically 32–64 elements, then:

1. Sorts each run using insertion sort (fast for small chunks)
2. Merges sorted runs using merge sort (efficient for large data)

This combination is why Python's sort is so fast in practice — it uses the right algorithm for each phase of the work.

# This uses Timsort (insertion sort + merge sort internally):
arr = [5, 2, 8, 1, 9, 3, 7, 4, 6]
arr.sort()
print(arr)
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Java's Arrays.sort() for primitive arrays uses a similar hybrid. Understanding insertion sort helps you understand why these production implementations work.

Key Takeaways

• Insertion sort builds a sorted portion incrementally, inserting each new element into its correct position
• Uses shifts (not swaps) — more efficient per operation than bubble sort
• O(n) best case on already-sorted or nearly-sorted data — a practical advantage
• O(n²) worst case — reverse sorted data, every element slides all the way left
• Beats merge sort and quicksort for small arrays due to cache efficiency and low overhead
• Stable and online (can sort a stream of arriving elements)
• The foundation of Timsort — Python's and Java's production sort algorithm

Next lesson: Merge Sort — where we finally break the O(n²) barrier with divide-and-conquer.