Insertion Sort: Simple, Stable, and Underrated

Pick up a hand of playing cards. Now sort them. Chances are, you didn't use merge sort or quick sort — you used insertion sort. You took each card and slid it into the right position among the cards you'd already organized.

That's insertion sort: simple, intuitive, and surprisingly practical.

How It Works

Insertion sort divides the array into two parts: a sorted portion (initially just the first element) and an unsorted portion (everything else). It picks the next unsorted element and inserts it into the correct position in the sorted portion.

Step by Step

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

Start: Sorted: [5] | Unsorted: [2, 8, 1, 9, 3]

Insert 2: Compare with 5. 2 is smaller, so shift 5 right and insert 2. → [2, 5, | 8, 1, 9, 3]

Insert 8: Compare with 5. 8 > 5, already in place. → [2, 5, 8, | 1, 9, 3]

Insert 1: Compare with 8 (shift), 5 (shift), 2 (shift). Insert at beginning. → [1, 2, 5, 8, | 9, 3]

Insert 9: Compare with 8. 9 > 8, already in place. → [1, 2, 5, 8, 9, | 3]

Insert 3: Compare with 9 (shift), 8 (shift), 5 (shift). 3 > 2, insert after 2. → [1, 2, 3, 5, 8, 9]

Done in 6 passes. Notice how elements that are already in the right place (like 8 and 9) require almost no work.

The Code

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr

The inner while loop shifts elements rightward until it finds the correct insertion point. The key is then placed in the gap.

Time Complexity

Space complexity: O(1) — sorts in-place with just one temporary variable.

The Best Case Is Special

When the array is already sorted, the inner loop never executes — each element is compared once to its predecessor and left in place. That's just n-1 comparisons: O(n).

This isn't just a theoretical curiosity. In practice, data is often nearly sorted: new items appended to a sorted list, data with minor perturbations, or output from a previous sort that's been slightly modified. Insertion sort handles all of these in nearly linear time.

Why Insertion Sort Still Matters

You might think: "Why bother with an O(n²) algorithm when O(n log n) algorithms exist?" Three reasons:

1. It's Fastest for Small Arrays

For arrays with fewer than ~20 elements, insertion sort is typically faster than merge sort or quick sort. The overhead of recursive calls, function setup, and complex logic in advanced algorithms exceeds the cost of insertion sort's simple comparisons and shifts.

This is why most real-world sorting implementations (including Python's Timsort and C++'s std::sort) switch to insertion sort for small sub-arrays. When quick sort or merge sort recurses down to a partition of 10-20 elements, it hands off to insertion sort for the final sorting.

2. Nearly Sorted Data

If the data has only a few elements out of place, insertion sort runs in nearly O(n) time. No other simple algorithm matches this:

• 1,000 elements with 5 swaps needed: ~1,005 operations
• Quick sort on the same data: ~10,000 operations (doesn't exploit near-sortedness)

3. Online Sorting

Insertion sort can sort data as it arrives — you don't need the full array upfront. As each new element comes in, insert it into the already-sorted portion. This makes it ideal for:

• Maintaining a sorted list with frequent insertions
• Processing streaming data
• Real-time systems where data trickles in

Properties

Stable: Equal elements maintain their relative order. This matters for multi-key sorting — if you sort students by grade, those with the same grade keep their alphabetical order.

In-place: O(1) extra memory. Just one temporary variable for the key being inserted.

Adaptive: Performance improves with pre-sortedness. The number of operations is proportional to the number of inversions (pairs of elements that are out of order).

Online: Can process elements one at a time as they arrive.

Insertion Sort vs Other O(n²) Algorithms

Insertion sort dominates bubble sort in almost every metric. Selection sort does fewer swaps (exactly n-1), which matters when swaps are expensive, but insertion sort is usually the better choice among simple algorithms.

The Connection to Binary Search

One optimization: use binary search to find the insertion point instead of linear scanning. This reduces comparisons from O(n) to O(log n) per element.

However, you still need to shift elements to make room — and shifting is O(n). So the overall complexity stays O(n²). The improvement is in comparisons, not moves.

For this reason, binary insertion sort is useful when comparisons are expensive (e.g., comparing long strings) but moves are cheap.

Shell Sort: Insertion Sort on Steroids

Shell sort generalizes insertion sort by comparing elements that are far apart, then progressively reducing the gap. By the time the gap reaches 1 (regular insertion sort), the array is nearly sorted, so the final pass is fast.

Shell sort achieves O(n^1.3) to O(n^1.5) depending on the gap sequence — a significant improvement over O(n²) while maintaining insertion sort's simplicity and in-place operation.

Practice These Concepts

See sorting in action with coding problems:

• Merge Sorted Array — Uses the same "insert into sorted portion" logic
• 3Sum — Sorting is the first step in the optimal solution

Related Articles

• Bubble Sort Explained with Visualizations — Another simple O(n²) sort, and why insertion sort usually beats it
• Big O Notation: A Practical Guide — Understand why O(n²) matters and when it's acceptable
• What is an Algorithm? The Complete Beginner's Guide — Start here if you're new to algorithms
• Merge Sort: Divide and Conquer Made Simple — See how O(n log n) algorithms handle larger datasets

See It In Action

Our interactive visualization shows insertion sort building the sorted portion one element at a time. Watch as each new element slides leftward past larger elements until it finds its place. The animation makes the "playing cards" metaphor come alive — you can see exactly why nearly-sorted data is so fast and why reverse-sorted data is the worst case.

Try different input patterns (sorted, reverse, random, nearly sorted) and see how dramatically the performance changes.