Day 32 · Lining up the kids

Sorting

You will be able to

Implement insertion sort and merge sort from scratch and explain their complexities
Explain quicksort's partition idea and its O(n²) worst case
Define stability and demonstrate why it matters for multi-key sorts
Explain why comparison sorting cannot beat O(n log n) and when counting sort escapes the bound
Apply the sort-then-solve pattern to simplify problems (merge intervals)

Today's ~120 minutes

Spaced-rep warm-up: due cards (graphs, heaps, Big O)	10 min
ELI5 + tech read; run the sort-race visualizer on 3 input shapes	18 min
Guided: implement & race, stability + counting sort + merge intervals	38 min
Practice: meeting rooms	20 min
Project: sorting field notes + eval-results sorter	24 min
Quiz + flashcards	10 min

Builds on: Day 22 — Big O & complexity · Day 27 — Recursion & divide/conquer

The analogy

🧸 ELI5⚙ Tech

A teacher lines up kids by height. The rookie method: take each kid and walk them backwards down the line until they slot in front of the first taller kid — insertion sort. Fine for a small class; agonizing for a stadium, because each kid may shuffle past half the line (that is the n² handshake feeling from Day 22).

The clever method: split the stadium into two halves, get each half lined up (however — split again, recursively!), then MERGE: both lines face you, and you repeatedly wave forward whichever front kid is shorter. Merging two sorted lines is one easy pass — that is merge sort, and the split-solve-merge shape is exactly Day 27's divide and conquer. Quicksort plays it differently: pick one kid (the pivot), send everyone shorter to the left and taller to the right, then repeat inside each side.

One more idea hides in plain sight: if two kids are the SAME height, does the line-up keep them in their original order? A method that does is called *stable* — it sounds like trivia until you sort by height *and then* by age and discover only stable sorts let the two orderings compose.

Why this matters on the job

You will almost never implement a sort in production — Python's Timsort has that covered — but sorting is the interview's favorite complexity playground, and "sort first, then the problem becomes easy" is a genuinely load-bearing pattern: merge intervals, meeting rooms, deduplication, ranking eval results (Day 140), ordering retrieved chunks by score before reranking (Day 117). Stability bites for real: sort a DataFrame by date then by customer, and whether within-customer date order survives depends on the sort being stable. Knowing WHY the default sort is O(n log n) — and when a counting sort beats it — is the difference between using tools and understanding them.

Watch it happen

Lining up the kids — insertion sort, card-player style

step 1 / 6

Insertion sort works like sorting a hand of cards: the left region is always sorted; take the next card and walk it left to its slot. One card (5) is trivially "sorted".

🎯 Predict modespeed1×

Guided practice

guided 1

Implement the three, race them

22 min

Create sorting_lab.py. Implement insertion_sort (in place) and merge_sort (returns a new list) — the starter gives merge scaffolding and a correctness checker against sorted().
Implement quicksort with a RANDOM pivot in the simple three-way-list style shown.
Race all three plus built-in sorted() on: random data (n = 2000), already-sorted data, reverse-sorted data. Before running, predict the ranking in each scenario and write it down.
Explain your two most interesting results out loud — expected: insertion sort wins on already-sorted (O(n)); a FIRST-element-pivot quicksort would die on sorted input (try it at n = 900 and watch for RecursionError — why ~900? Python's recursion limit).
Note how absurdly fast sorted() is — C-speed Timsort. State when you would still hand-roll: never in production; always in interviews.

🐍 python — editable, runs in your browser

import random, time

def insertion_sort(a):
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= keeps it STABLE
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)
    lt = [x for x in a if x < pivot]
    eq = [x for x in a if x == pivot]
    gt = [x for x in a if x > pivot]
    return quicksort(lt) + eq + quicksort(gt)

for name, data in [("random", [random.randint(0, 9999) for _ in range(2000)]),
                   ("sorted", list(range(2000))),
                   ("reversed", list(range(2000, 0, -1)))]:
    for fn in (insertion_sort, merge_sort, quicksort, sorted):
        arr = list(data)
        t0 = time.perf_counter()
        result = fn(arr)
        ms = (time.perf_counter() - t0) * 1000
        assert list(result if result is not None else arr) == sorted(data)
        print(f"{name:9s} {fn.__name__:15s} {ms:8.2f} ms")

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

Stability you can see + counting sort

16 min

Build the starter's list of (name, grade) tuples. Sort by name first, then sort THAT result by grade using key=. Print it: within each grade, names are still alphabetical. That composition is stability at work — Python guarantees it.
Now shuffle and sort by grade in ONE pass with key=lambda p: (p[1], p[0]) — the tuple-key trick. Confirm it matches the two-pass result, and note when each style wins (two stable passes when the sorts happen at different times/places; tuple key when you control one call).
Implement counting_sort(scores) for exam scores 0–100. Race it against sorted() on one million random scores. Say precisely why comparing was never necessary: the key space is tiny and known.
Classic — merge intervals (sort-then-solve): given [[1,3],[8,10],[2,6],[15,18]], merge overlaps. Think aloud: "Unsorted, every interval might overlap any other — O(n²) checks. Sorted by start, overlaps can only be adjacent: one linear pass, extending or appending." Implement and test with touching intervals like [1,4],[4,5].

🐍 python — editable, runs in your browser

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

Meeting rooms

20 min

Part 1: given meeting intervals, can one person attend them all? Part 2 (the real question): what is the MINIMUM number of rooms needed to host all meetings?

Constraints: aim for O(n log n); brute-force pairwise checking is disqualified. Test with back-to-back meetings ([1,5],[5,8] need one room) and a triple overlap.

Hints (only if stuck): Part 1 is merge-intervals thinking — sort by start, look for any overlap between neighbors. Part 2 has two elegant solutions: (a) a min-heap (Day 30!) of room end-times — reuse the room that frees earliest; (b) sort starts and ends separately and sweep with two pointers (Day 24). Implement one, understand both.

Ship before you stop

Sorting field notes + the eval-results sorter

Two parts in your practice repo. (1) dsa/sorting.py: today's implementations plus merge_intervals and meeting rooms, tested. (2) sort_evals.py, a taste of Day 140: given the provided CSV of mock eval results (columns: model, task, score, latency_ms), print a leaderboard sorted by score DESCENDING with latency ASCENDING as tiebreak — one sorted() call with a clever key — plus a per-task top-3 using the stable two-pass composition. Add a docstring explaining which sorts had to be stable and why. Commit both.

Rubric — check what you completed (0/6)

Insertion, merge, and quicksort all pass the correctness checker on random/sorted/reversed/duplicate-heavy inputsRace table recorded with a one-line explanation of each rankingmerge_intervals handles touching intervals ([1,4],[4,5]) correctlyLeaderboard sorts descending-score with ascending-latency tiebreak in one sorted() callStability explanation in the docstring names where an unstable sort would corrupt resultsCommitted with tests green

Common mistakes & misconceptions

Writing comparison logic by hand when key= does it: sorted(rows, key=lambda r: (-r.score, r.latency)) beats any manual comparator.
Assuming quicksort is always O(n log n). Bad pivots (first element on sorted data) hit O(n²); random or median-of-three pivots are the fix.
Forgetting merge sort's O(n) extra space when the interviewer asks "can you sort in place?" — quicksort and heapsort can; classic merge sort cannot.
Believing O(n log n) is the floor for ALL sorting. It is the floor for COMPARISON sorting; counting/radix escape when keys are small integers.
Using strict < in a merge and silently losing stability — equal elements must prefer the LEFT run (<=).
Sorting when a heap answers the actual question: "top 10 of a million" wants Day 30's O(n log k) heap, not an O(n log n) full sort.

Knowledge check

Q1. You sort employee rows by hire date, then stably sort by department. What is true of the result?

Q2. Why can no comparison sort beat O(n log n) in the worst case?

Q3. A million integer scores in 0–100 need sorting. The strongest choice?

Go deeper — curated resources

toolVisuAlgo — Sorting race visualization ↗20 min bookOpenDSA — Sorting chapter ↗25 min courseCS50x Week 3 — Algorithms (sorting segment) ↗30 min

If you have a third hour

Timsort's run detection — Timsort scans for pre-sorted "runs" and merges them cleverly. Skim the algorithm's description and connect it to why your already-sorted benchmark was near-instant.

Done means

All three sorts pass correctness checks; race results recorded and explained
Stability composition demonstrated and explained in your own words
Meeting rooms solved at O(n log n) with the approach named
Eval-results sorter committed with the stability docstring
Quiz ≥ 2/3

How this connects

← Back: Merge sort is Day 27's divide-and-conquer made concrete, the race harness is Day 22's timing lab, and meeting rooms reunites Day 30's heap with Day 24's two pointers.

Forward →: Day 33 exploits what sorting buys: binary search only works on sorted data. Day 66's pandas sort_values inherits stability semantics, Day 117 sorts retrieved chunks by rerank score, and Day 140's eval reports are the leaderboard you just built, for real.

Unlocks: D33 Binary Search & Variants