Elementary sorts: bubble, insertion, selection

What this chapter covers

Sorting is the most-studied problem in computing, and it starts here, with three sorts simple enough to write from memory: bubble, selection, and insertion. All three are O(n²), which sounds like a reason to skip them — but two things make them worth a chapter. First, they're the baseline the fast sorts are measured against, so you can't appreciate O(n log n) without feeling O(n²). Second, one of them — insertion sort — is genuinely useful: it's near-linear on nearly-sorted data and lives inside the standard library's sort. This chapter builds all three and races them against Timsort.

A bit of history

Sorting is as old as data processing — mechanical card sorters ran versions of these algorithms before electronic computers existed. The names are mostly folklore; "bubble sort" appears in print by 1962, though the technique is older. What crystallized the field was Donald Knuth's 1973 volume "Sorting and Searching," which analyzed these and dozens more with a rigor that made sorting the canonical example for teaching algorithm analysis — which is exactly the role it plays in this book. And the elementary sorts aren't purely historical: in 2002 Tim Peters designed Timsort for Python by combining merge sort with insertion sort, because insertion sort is unbeatable on the small, nearly-ordered pieces that real data breaks into. The oldest sort in the chapter is a live component of the newest.

The intuition

Each of the three has a one-sentence idea. Bubble sort walks the array swapping adjacent out-of-order pairs; after each pass the largest unsorted element has "bubbled" to its place at the end. Selection sort finds the smallest element of the unsorted part and swaps it to the front, then repeats on the rest. Insertion sort grows a sorted prefix on the left: it takes the next element and slides it back past everything larger, dropping it into place — the way you sort a hand of playing cards.

They're all O(n²) because each does about n passes with about n work per pass, but they differ in temperament. Selection always does the full n² comparisons even on sorted input, but only n swaps. Bubble can quit early if a pass finds nothing to swap. And insertion does the least work when the data is already close to sorted, because each element barely has to move — which is the property that makes it matter.

Complexity: how it scales

All three sorts are $O(n^2)$ on average and in the worst case — the nested loops give it away, about $n^2/2$ comparisons. Their best cases differ: bubble and insertion drop to $O(n)$ on already-sorted input (bubble via its early-exit flag, insertion because the inner loop never runs), while selection stays $O(n^2)$ no matter what, since it always scans the whole unsorted part to find the minimum. All three are in-place, $O(1)$ extra space. The chart puts the three against Timsort; the elementary sorts trace the unmistakable upward curve of a quadratic while Timsort hugs the floor:

At just 2000 elements, insertion sort took about 42 ms against Timsort's 0.08 ms — 500 times slower — and that ratio grows without bound as n increases, because it's a complexity-class gap, not a constant. That's the whole case for the next chapters.

What it's good at, what it isn't

The elementary sorts are the right choice in exactly one situation: small or nearly-sorted arrays, where insertion sort's low constant factor and adaptivity beat a fancier sort's overhead. This isn't hypothetical — it's why production sort routines switch to insertion sort once a subarray gets small (often around 16–64 elements). They're also simple, in-place, and (for insertion and bubble) stable, meaning equal elements keep their order.

For anything else — large arrays of random data — they're the wrong tool, decisively. O(n²) means doubling the input quadruples the time, so they cross from "instant" to "unusable" fast. Selection sort in particular has no redeeming best case. The rule is simple: reach for insertion sort on the small and the nearly-ordered, and reach for an O(n log n) sort for everything else.

The data, or the inputs

The face-off sorts random integer arrays at growing sizes, so the quadratic curve is unmissable. A second measurement feeds insertion sort two kinds of input at the same size — fully random and nearly sorted — to isolate its adaptivity. And the animation runs insertion sort on ten elements, slow enough to watch the sorted prefix grow one insertion at a time.

Build it, one function at a time

Bubble sort — swap adjacent pairs, pass after pass, with an early exit when a pass is clean:

def bubble_sort(a):
    """O(n^2): repeatedly walk the array swapping adjacent out-of-order pairs, so
    the largest element 'bubbles' to the end on each pass. The early-exit flag
    makes it O(n) on already-sorted input — a pass with no swaps means done."""
    a = list(a)
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

Selection sort — find the minimum of the rest, swap it into place; n swaps, always n² comparisons:

def selection_sort(a):
    """O(n^2): each pass scans the unsorted part for its minimum and swaps it into
    place. It does only n swaps (good when writes are expensive) but always n^2/2
    comparisons — there's no early exit, sorted input costs the same as random."""
    a = list(a)
    n = len(a)
    for i in range(n):
        lo = i
        for j in range(i + 1, n):
            if a[j] < a[lo]:
                lo = j
        a[i], a[lo] = a[lo], a[i]
    return a

Insertion sort — the important one — grows a sorted prefix by shifting each new element back into its spot:

def insertion_sort(a, probe=None):
    """O(n^2) worst, O(n) best: grow a sorted prefix by taking each next element
    and shifting it left past everything larger, into its slot. On nearly-sorted
    data every element barely moves, so it's close to linear — which is why it's
    the sort of choice for small or almost-ordered arrays."""
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]                 # shift the larger element right
            j -= 1
            if probe is not None:
                probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
        a[j + 1] = key                      # drop the key into its place
        if probe is not None:
            probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
    return a

Watch it work

Here's insertion sort on ten bars. Blue is the sorted prefix, orange is the element currently being inserted, gray is the untouched tail. Step through it and watch the blue region grow from the left one element at a time: each frame takes the first gray bar and slides it left through the blue region until it's in order. On this random input it does a fair amount of shifting — but picture the bars already nearly sorted, and you'd see each orange bar drop almost straight into place with barely any movement. That difference is the adaptivity:

The complete code

Both versions in one place — flip between them. The from-scratch tab has all three elementary sorts. The library tab is sorted, which is Timsort — and remember, Timsort has insertion sort inside it for the small runs, so this isn't quite a fair fight: you built a piece of the library sort.

"""The three elementary sorts — bubble, selection, and insertion. All O(n^2), all
short enough to hold in your head, and all worth knowing precisely because they're
where sorting starts and where the O(n log n) sorts earn their keep by contrast.

They differ in character: bubble swaps neighbors, selection finds the minimum each
pass, insertion grows a sorted prefix. Insertion is the one that matters in
practice — it's genuinely fast on nearly-sorted data and is what real libraries use
for small arrays.
"""


# region: bubble
def bubble_sort(a):
    """O(n^2): repeatedly walk the array swapping adjacent out-of-order pairs, so
    the largest element 'bubbles' to the end on each pass. The early-exit flag
    makes it O(n) on already-sorted input — a pass with no swaps means done."""
    a = list(a)
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a
# endregion


# region: selection
def selection_sort(a):
    """O(n^2): each pass scans the unsorted part for its minimum and swaps it into
    place. It does only n swaps (good when writes are expensive) but always n^2/2
    comparisons — there's no early exit, sorted input costs the same as random."""
    a = list(a)
    n = len(a)
    for i in range(n):
        lo = i
        for j in range(i + 1, n):
            if a[j] < a[lo]:
                lo = j
        a[i], a[lo] = a[lo], a[i]
    return a
# endregion


# region: insertion
def insertion_sort(a, probe=None):
    """O(n^2) worst, O(n) best: grow a sorted prefix by taking each next element
    and shifting it left past everything larger, into its slot. On nearly-sorted
    data every element barely moves, so it's close to linear — which is why it's
    the sort of choice for small or almost-ordered arrays."""
    a = list(a)
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]                 # shift the larger element right
            j -= 1
            if probe is not None:
                probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
        a[j + 1] = key                      # drop the key into its place
        if probe is not None:
            probe.append({"arr": list(a), "key_pos": j + 1, "sorted_to": i})
    return a
# endregion

"""Python's `sorted` (and `list.sort`) is Timsort — an O(n log n) hybrid of merge
sort and insertion sort, designed by Tim Peters in 2002 for CPython. It finds runs
of already-ordered data and merges them, and it uses insertion sort (this chapter's
insertion_sort) for the small pieces. So the elementary sorts aren't just baselines
to beat — insertion sort is a component inside the library sort.

The face-off is our three O(n^2) sorts against Timsort's O(n log n).
"""


# region: sort_builtin
def sort_builtin(a):
    """Timsort: O(n log n) worst case, adaptive (near-linear on nearly-sorted or
    already-sorted input), stable, implemented in C."""
    return sorted(a)
# endregion

Scratch vs library

The headline is the 500× gap at n = 2000 — O(n²) against O(n log n), the reason the rest of this tier exists. But the more interesting number is insertion sort against itself. On 8000 random elements it took about 710 ms; on 8000 nearly-sorted elements, about 38 ms — nineteen times faster on the same amount of data, purely because the data was almost in order. That's adaptivity made concrete, and it's why insertion sort survives inside a modern library sort while bubble and selection are teaching tools. Timsort's whole strategy is to find the nearly-sorted runs that real data contains and let insertion sort finish them cheaply.

Where you'll actually meet it

You'll rarely call one of these directly, but you use insertion sort constantly without knowing — it's inside every sorted() call, finishing the small runs. Beyond that, insertion sort is the natural way to keep a small list sorted as items arrive (inserting each into place), which is how you'd maintain a leaderboard of the top few or merge a small sorted batch into a larger one. And the elementary sorts remain the canonical first example in every algorithms course, because they're where you learn to read a nested loop as a quadratic — a skill you'll use in code review far more than you'll ever write bubble sort.

Takeaways

The three elementary sorts are all $O(n^2)$ and in-place: bubble swaps neighbors, selection picks the minimum each pass, insertion grows a sorted prefix. Insertion is the one worth keeping, because it's adaptive — near $O(n)$ on nearly-sorted data — which makes it the right sort for small or almost-ordered arrays and a working part of the library's Timsort. The other two are baselines: know them so you recognize a quadratic when you see one.

That recognition is the point of the chapter, because the next three sorts exist to escape the quadratic. Merge sort, quicksort, and heapsort all hit $O(n \log n)$ by splitting the problem instead of grinding through every pair — the divide-and-conquer recursion from the last chapter, applied to sorting. Merge sort is next.