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: selects the minimum for each remaining position. It uses at most O(n) swaps and often writes less than bubble sort, but it does not universally minimize swaps among all sorting algorithms. Comparisons remain O(n²).
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 adaptive on nearly sorted data and has low overhead. Those properties make insertion-sort variants useful for small partitions inside hybrid sorts. It is not guaranteed to be the fastest for every small array; thresholds depend on implementation, element type, and hardware.

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