Insertion Sort

Jr Codex DSA Notes

Level: Beginner Prerequisites: Chapter 2 Time to complete: ~20 minutes

The Idea: Build a Sorted Prefix
Implementation
Complexity — Best, Average & Worst
Why Insertion Sort Shines on Nearly-Sorted Data
Stability
Summary & Next Steps

1. The Idea: Build a Sorted Prefix

Insertion sort grows a sorted prefix one element at a time — like sorting a hand of playing cards, picking up one card and inserting it into its correct position among the cards already in your hand.

[3, 1, 2] → sorted prefix grows left to right:
[3 | 1, 2]        prefix: [3]
[1, 3 | 2]        insert 1 before 3 → prefix: [1, 3]
[1, 2, 3 | ]       insert 2 between 1 and 3 → prefix: [1, 2, 3]

2. Implementation

def insertion_sort(items):
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]     # shift larger elements right
            j -= 1
        items[j + 1] = current           # drop `current` into its correct slot
    return items

3. Complexity — Best, Average & Worst

Case	Scenario	Complexity	Why
Best	Already sorted	`O(n)`	The `while` loop condition fails immediately every time — one comparison per element, no shifting
Average	Random order	`O(n²)`	Roughly half the prefix shifts, on average, for each insertion
Worst	Reverse sorted	`O(n²)`	Every new element must shift past the entire sorted prefix

Space: O(1) — sorts in place.

This best-case behavior directly echoes Module 1, Chapter 5's discussion of why the same algorithm can have wildly different complexities depending on input shape.

4. Why Insertion Sort Shines on Nearly-Sorted Data

Because insertion sort's cost is driven by how far each element has to shift, data that's already close to sorted requires very little shifting — its real-world performance on nearly-sorted input can rival O(n) algorithms, even though its worst case is O(n²). This makes it genuinely useful (not just an academic warm-up) in two situations:

Small arrays — for small n, the constant-factor simplicity of insertion sort often beats the overhead of more complex O(n log n) algorithms. This is exactly why production sorting algorithms (Chapter 6) switch to insertion sort for small sub-arrays internally.
Nearly-sorted or incrementally-updated data — appending a few new elements to an already-sorted collection and re-sorting is cheap with insertion sort, since most elements need zero shifting.

5. Stability

Insertion sort is stable — an element is only shifted past elements strictly greater than it, so equal elements never cross past each other, preserving their original relative order (Chapter 2, Section 6).

6. Summary & Next Steps

Key Takeaways

Insertion sort builds a sorted prefix by inserting each new element into its correct position among the elements already processed.
Best case is O(n) (already sorted, no shifting needed); average and worst case are O(n²).
It's genuinely useful in practice for small arrays and nearly-sorted data — not just a teaching tool.
It's stable, like bubble sort.

Concept Check

Why does insertion sort achieve O(n) on already-sorted data, unlike selection sort?
What characteristic of input data makes insertion sort perform close to linearly, even though its worst case is quadratic?
Why might a production sort library use insertion sort internally for small sub-arrays, even though it's O(n²) in general?

Next Chapter

→ Chapter 4: Merge Sort

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index