The Simple Sorts: Bubble, Selection, Insertion

"Everyone learns bubble sort and then learns to sneer at it. But one of these 'slow' O(n²) sorts is quietly inside the fast sorts you actually use — because on small or nearly-sorted data, simple beats clever."

The Three Teaching Sorts

All three are O(n²) — they compare pairs in nested loops — but each illustrates a different idea:

Bubble sort: repeatedly swap adjacent out-of-order pairs; the largest 'bubbles' to the end each pass. The simplest to picture, almost never the right choice in practice — its main job is being the first sort everyone meets.
Selection sort: each pass finds the minimum of the unsorted region and places it. Minimizes the number of swaps (useful if writes are expensive) but always O(n²) comparisons.
Insertion sort: builds a sorted prefix one element at a time, inserting each new element into its place — exactly how most people sort a hand of cards.

Why Insertion Sort Earns Its Keep

Insertion sort is the one that matters, because it has two real virtues the others lack. First, it's adaptive: on already-sorted or nearly-sorted data, each new element is already (almost) in place, so it does only O(n) work — not O(n²). Second, it has tiny constant overhead: no recursion, no extra memory, great cache behavior. That combination makes it the fastest sort for small arrays. So the world's best sorts — Python's Timsort, C++'s introsort — divide big data with merge/quicksort but switch to insertion sort for the small subarrays at the bottom. The 'slow' sort is a component of the fast ones.

Bubble/selection/insertion are all O(n²), but insertion sort is special: adaptive (O(n) on nearly-sorted data) and low-overhead, making it the fastest choice for small arrays. That's why production sorts use it as the base case. 'Slow' has niches; don't dismiss it blindly.

When Simple Is Right

The judgment: for large, random data, never reach for these — O(n²) on a million items is a trillion operations. But for small arrays (say under ~50 elements), nearly-sorted data, or when code simplicity and low memory matter more than asymptotics, insertion sort can genuinely win. This is the recurring quest theme one more time: the 'best' algorithm depends on the data and the scale, and dismissing a simple tool wholesale is as much an error as over-engineering with a fancy one.

Pippa's Confession

I confidently 'knew' insertion sort was obsolete — why use O(n²) when merge sort is O(n log n)? Then Dad showed me that Python's own Timsort calls insertion sort on small runs, because for tiny arrays its low overhead beats merge sort's bookkeeping. I'd mistaken 'worse asymptotic complexity' for 'never useful.' The constants Big-O throws away are exactly what make insertion sort the right tool at small scale — a humbling reminder that asymptotics aren't the whole story.

Code

Insertion sort — the one worth keeping·python

# Insertion sort: the genuinely useful simple sort. Adaptive + low overhead.
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:    # shift bigger elements right
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key                  # drop key into its slot
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))   # [1, 2, 3, 4, 5, 6]

# The adaptive win: on nearly-sorted data, the inner while barely runs.
nearly = [1, 2, 3, 5, 4, 6]    # only one element out of place
# Each element finds its spot in ~1 step -> close to O(n), not O(n^2).

# Selection sort (minimizes swaps) and bubble sort (simplest to picture)
# are both always O(n^2) comparisons — mostly pedagogical, rarely the right pick.
# Production sorts (Timsort) use INSERTION sort for their small base cases.

Exercise

Explain why insertion sort runs in roughly O(n) on an already-sorted array but O(n²) on a reverse-sorted one — trace what the inner while-loop does in each case. Then explain why Python's Timsort bothers to use insertion sort for small chunks instead of just merge-sorting everything.

Hint

On sorted data the inner while never shifts (each key is already ≥ its predecessor), so it's ~n total steps. On reverse-sorted data every key shifts all the way left → ~n²/2. Timsort uses insertion sort on small runs because its low constant overhead beats merge sort's recursion/allocation cost at tiny sizes.

The Three Teaching Sorts

Why Insertion Sort Earns Its Keep

When Simple Is Right

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0