Sorting: Insertion, Merge, and Quicksort

Three weeks of machinery, and this is the payoff. This week we meet three ways to put things in order: one that works like a person sorting a hand of cards, one that splits the job in half over and over, and one that gambles a little and usually wins big. All three are short enough to fit on an index card — and all three are in Project 1, where you will build them, race them, and watch the n² and n log n curves from Notes 02 come to life on your own machine.

Session planHow we will spend the two sessions

Section 1Why sorting matters

Pick up a shuffled deck and deal yourself seven cards. Without thinking about it, you will arrange them — low on the left, high on the right. Nobody taught you an algorithm for this. You do it because a sorted hand is usable: you can see what you have, spot what is missing, and find any card instantly. That instinct is the whole subject of this week. Sorting means exactly what it sounds like: take a list of items that can be compared, and rearrange the same items so they run from smallest to largest.

Why spend two full sessions on it? Because sorted data is a superpower, and you have already seen the proof. In Notes 02 we met binary search — the halving trick that finds one item among a million in about 20 looks instead of a million. But binary search has a strict entry requirement: the list must already be sorted. Jump to the middle of an unsorted list and the value there tells you nothing about which half to keep. Sorting is the fee you pay to unlock halving.

It goes beyond searching. Finding duplicates, finding the median, lining two datasets up against each other, showing a human a readable report — all of these are easy on sorted data and annoying on unsorted data. That is why sorting is the most-run family of algorithms in the world, and why it is the classic first test bed for algorithm design: the problem is dead simple to state, everyone agrees on what a right answer looks like, and yet the solutions span the whole range from "fine for a hand of cards" to "fine for a billion records."

Section 2Insertion sort: how you already sort cards

Watch someone pick up cards one at a time, and you will see the first algorithm of the week performed perfectly by a person who has never heard its name. They hold the cards already picked up in sorted order. Each new card gets walked leftward past bigger cards until it reaches its spot, and slots in. That is the entire algorithm. It is called insertion sort, because each new item gets inserted where it belongs.

Here is the full run on six numbers. One card is picked up per row; green is the sorted part, blue is the card that just landed, faded cards have not been picked up yet.

What it costs, in plain terms

Look at the two extreme rows above. When 6 was picked up it was already in place: one comparison, done. When 1 was picked up it had to walk past every single sorted card. That spread is the whole cost story of insertion sort:

• Worst day: about n² work. Feed it a reversed list and every card walks past everything picked up so far — the first card walks past 1 card, the next past 2, then 3, and so on up to n−1. Add that staircase up and you get roughly half of n². Notes 02 taught us to shrug at the half: this is n² behavior, and doubling the list quadruples the work.
• Best day: about n work. Feed it an already-sorted (or nearly sorted) list and every card checks one neighbor, says "I'm fine," and stays put. One comparison per card — the algorithm is basically just verifying, and verifying is cheap.

That second bullet is not a consolation prize; it is insertion sort's career. Real data is very often almost sorted — yesterday's sorted file with today's handful of new rows, a leaderboard after one game. On data like that, insertion sort beats everything else in these notes. And on tiny lists — a few dozen items — its dead-simple inner loop makes it the fastest thing available, period. Remember the crossover demonstration at the end of Notes 02, where the n² algorithm won the small-n race because of its lean constant? That n² algorithm was this one.

Now drive it yourself. Step insertion sort through the shuffled cards and watch the comparison counter — then switch to nearly sorted and watch how little it does. The Merge and Quick buttons will make sense by the end of these notes; come back and race them on the same cards.

Section 3Divide and conquer: the idea

Insertion sort works one card at a time, and pays for it: the sorted hand keeps growing, so each new card has more and more to walk past. The next idea attacks that head-on, and it is bigger than sorting — it is one of the great algorithm-design strategies of the course.

You have been on the receiving end of this idea your whole life. Looking up a word in a paper dictionary is divide and conquer: open near the middle, keep the correct half, repeat. Binary search is divide and conquer, with a combine step so easy it is invisible. And you have already priced the idea, too: last week's recursion trees were exactly a picture of a problem splitting into halves, level by level, until it hit the tiny base cases at the bottom. Notes 03 even had a name for the pattern "split in two halves, then do a full pass of work to combine" — we called it the sort silhouette, and its price tag came out to Θ(n log n). This week you finally meet the algorithm that silhouette belongs to.

What makes divide and conquer pay off for sorting is a happy asymmetry: splitting a list is trivial, and combining two sorted lists is nearly as easy. The hard problem — sorting — never actually gets solved head-on. It gets postponed, halved, and postponed again, until the pieces are one item long, and a one-item list is already sorted, no work required. All the real effort goes into the combine step, and the combine step, as you are about to see, is a pleasure.

Section 4Merge sort: zip two piles

Start with the combine step, because it is the heart of the whole algorithm. Suppose you have two piles of cards, each already sorted, smallest card on top. How do you merge them into one sorted pile? You do not need to search or think. Look at the two top cards. The smaller one — whichever pile it came from — is the smallest card anywhere, so it goes down first. Repeat. When one pile runs out, the other slides over as-is, for free.

That is called a merge, and it has a lovely property: every comparison places one card for good. No card is ever picked up twice, no comparison is ever wasted. Merging two piles totaling n cards costs at most n−1 comparisons — a single cheap pass. Step through it:

Merge sort is just this move, applied with divide-and-conquer scaffolding around it. Split the list in half. Sort each half (how? split it in half — and so on down, until the pieces are single cards, which are sorted by definition). Then merge your way back up: pairs of single cards merge into sorted runs of two, runs of two merge into runs of four, and so on until one final merge produces the whole sorted list. Watch it in the sorting lab — press Merge and step: you will see it split all the way down first, then zip runs together on the way back up.

Why n log n — a picture, not a proof

Here is why you should believe it, in three plain sentences. Every level of the picture does about n work, because merging touches each card once and every card is in exactly one merge per level. There are only about log n levels, because you can only cut a pile in half so many times before the pieces are single cards — about 20 times for a million items. Small bill per floor, very few floors: n log n. (This is the same answer the recurrence machinery of Notes 03 gave the sort silhouette — the picture and the algebra agree, which is always a good sign.)

And notice what merge sort does not care about: the input. Shuffled, sorted, reversed — it splits and merges the exact same way, does the same n log n work, every single time. Try all three presets in the lab and watch the comparison counter barely move. That steadiness is merge sort's personality: no great days, no terrible days, a dependable professional. Its one vice is that merging needs a second array to zip into, so it uses extra memory proportional to n.

Section 5Quicksort: split the room

Merge sort splits blindly down the middle and does all its thinking while combining. Quicksort is its mirror image: it does the thinking while splitting, and then the combine step is nothing at all.

Picture sorting a room full of people by height. Pick one person — call them the pivot. Everyone shorter, go stand to their left; everyone taller, to their right. One pass through the room, and something quietly wonderful has happened: the pivot is standing in their exact final position — every person who belongs to their left is somewhere on the left, everyone else on the right — and they never have to move again. The two groups still need sorting, but they never need to interact: sort the left group the same way, sort the right group the same way, and the room is sorted. No merge, no second array, nothing to combine. The list sorts itself in place.

Luck, in pictures

Everything about quicksort's cost comes down to one question: how even are the splits?

So which do you get? Here is the surprise the lab is hiding: press Quick on the nearly sorted or reversed cards. Our lab's quicksort always picks the last card of the range as its pivot — and on sorted-ish input the last card keeps being the biggest or smallest thing in its range, the exact unlucky picture above. Sorted input, the easiest case imaginable for insertion sort, is naive quicksort's worst nightmare. Algorithms have personalities, and they do not agree on which inputs are easy.

The fix is one sentence long, and it is genuinely one of the best ideas in the course: pick the pivot at random. A random card almost never lands near the extremes over and over — the streak of bad luck needed for n² behavior becomes astronomically unlikely, no matter how the input is arranged, and doesn't even need perfect splits: a pivot that lands anywhere in the middle half of the values still gives log-ish floors. Shuffle away the bad luck, and quicksort runs at n log n essentially always.

Why does everyone love it, when merge sort has the same n log n bill and a better guarantee? Because quicksort's constant factor is beautiful. It sorts in place — no second array to allocate and copy into. Its inner loop is a tight little scan that hardware happens to execute extremely fast. In practice, on big shuffled data in memory, a good quicksort is usually the fastest comparison sort there is — which is exactly the kind of claim Project 1's benchmark harness lets you check instead of taking on faith.

Section 6Choosing your sort

Three sorts, three personalities. Here they are side by side — this table is worth more than any single fact in these notes, and Project 1's write-up will essentially ask you to reproduce it from your own measurements.

Notice that there is no "best sort" row. That is not diplomatic fence-sitting; it is the actual answer. The right sort depends on the size of the data, its shape (shuffled? nearly sorted?), where it lives, and what you are willing to risk. Learning to ask those questions is worth more than memorizing any answer — and it is precisely the selection-and-justification skill this course grades.

Section 7The code

Everything above, in Python. These are written to be read: each one is the analogy from its section, translated line by line. They are also deliberately plain — your Project 1 versions can start exactly here, and your benchmark harness will tell you what polish is worth.

Insertion sort

def insertion_sort(a):
    """Sort the list a in place, smallest first, and return it."""
    for i in range(1, len(a)):
        card = a[i]               # the card we just picked up
        j = i - 1
        # walk left: every card bigger than ours slides one place right
        while j >= 0 and a[j] > card:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = card           # drop the card into the gap that opened
    return a

One subtlety worth seeing: the card being inserted is lifted out into card, bigger cards slide right into the space it left, and it drops into the final gap. That is fewer moves than swapping it leftward one neighbor at a time — same algorithm, better constant. On nearly-sorted input the while loop almost never fires, which is the "best day: n" story in one line of code.

Merge sort

def merge(left, right):
    """Zip two sorted lists into one sorted list."""
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   # compare the two front cards…
            out.append(left[i])   # …the smaller one goes down next
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])          # one pile is now empty —
    out.extend(right[j:])         # the other slides over for free
    return out

def merge_sort(a):
    """Sort a list, smallest first. Returns a new list."""
    if len(a) <= 1:            # one card is already sorted — the base case
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]),   # sort the left half,
                 merge_sort(a[mid:]))   # sort the right half, zip them

Four lines of scaffolding around one honest worker. Cover merge with your hand and merge_sort reads exactly like §3's three verbs: split, solve, combine. The <= in the comparison (rather than <) is a quiet promise: when two cards tie, the left pile's card goes first, so items that compare equal keep their original order. That property is called stability, and Week 5 shows why report writers care about it.

Quicksort — a sketch

import random

def quicksort(a):
    """Sort a list, smallest first. Returns a new list.

    A teaching sketch: maximally clear, not maximally fast.
    Project 1 asks for the in-place version, which partitions
    within the array instead of building three new lists.
    """
    if len(a) <= 1:
        return a
    pivot = random.choice(a)      # the one-line fix for bad luck (§5)
    smaller = [x for x in a if x < pivot]
    equal   = [x for x in a if x == pivot]
    bigger  = [x for x in a if x > pivot]
    return quicksort(smaller) + equal + quicksort(bigger)

Read it as the room of people: pick someone at random, split into shorter and taller, sort each group, stand them back together. This version spends memory it does not need to — three fresh lists per call — which is why Project 1 asks for the in-place partition you watched in the sorting lab. But as a statement of the idea, it is hard to beat five lines.

Section 8Before next session

Next week, sorting part two: a sort that runs inside a clever data structure (heapsort), the counting argument that proves n log n is the wall for every comparison sort — and then the cheats that tunnel under the wall by not comparing at all. That is Notes 05.