Speaker note: Today we sort the same array eleven different ways, and count exactly what each one costs. By the end, "which sort should I use" has a real, numeric answer.
Speaker note: Fourteen short animations carry the whole lecture; every algorithm gets a normal run and at least one edge/hard run, right where it is introduced.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: This week is, above all, an exercise in Big-O — you will watch the numbers diverge in real time.
Speaker note: Heap sort does not get its own section today — you already earned it — but it reappears as the reference point all afternoon.
Speaker note: Both ideas will reappear constantly for the rest of this course and the next.
Speaker note: Every box on this map gets its own slides below, most with a short animation and a complete C/Java program.
Speaker note: Give them a moment — the answer sets up the whole second half of the lecture.
Speaker note: This is the single biggest idea shift of the week: from "compare and narrow" to "compute the address".
Speaker note: Section 1 sets up the two numbers — comparisons and writes — that every algorithm today will be measured by.
Speaker note: Because "rearrange the array" leaves enormous room for how: memory budget, what you already know about the input, whether ties may move.
Speaker note: That last freedom — stability — turns out to matter a great deal, and gets its own full section (11) later today.
Speaker note: These two numbers do not always agree on a winner — Section 12's animation puts five algorithms side by side to show exactly that.
Speaker note: A stable sort on students-by-grade leaves every same-grade group in their prior (name) order; an unstable one may shuffle them.
Speaker note: Time and space are always a trade-off — Section 13 ends the week with a decision table instead of one winner.
Speaker note: Section 2 opens the simple O(n²) family with the most intuitive idea: compare neighbors, swap if wrong, and know when to stop.
Speaker note: Surprisingly far, if you add one refinement: noticing when a whole pass made no swaps at all.
Speaker note: Only the discipline of noticing "a pass made zero swaps, stop" turns it from a curiosity into something worth teaching.
Speaker note: Every pass settles one more maximum at the tail; the early-exit flag is the one thing that makes this worth teaching.
Speaker note: Normal example: 10 unordered values — watch the counters on the right and the "settled" brace grow from the tail.
Speaker note: One pass, zero swaps, early exit — this is bubble sort's O(n) best case, made visible.
Speaker note: `n - 1 - pass` shrinks the inner loop every pass — the tail is already settled and never re-checked.
Speaker note: Without the flag, bubble sort is always O(n²) — the flag is the entire reason it is worth teaching.
Speaker note: Point them at the comparison operator itself.
Speaker note: Change that one operator to `>=` and stability is gone, with no change to the sorted result itself.
Speaker note: Section 3 trades bubble sort's many small swaps for a different cost profile: full scans, but the fewest writes possible.
Speaker note: You still scan the whole remainder every time — no early exit is possible — but you write far less.
Speaker note: It is the clearest example this week of trading comparisons for writes — see Section 12's empirical numbers.
Speaker note: No early exit is possible: finding the true minimum requires checking every remaining candidate, sorted or not.
Speaker note: Normal example: watch `min_idx` update as the scan finds smaller candidates, then the single swap into place.
Speaker note: Still the full n(n-1)/2 comparisons, and zero swaps — no early exit exists here, unlike bubble sort.
Speaker note: The swap is skipped entirely when i is already the minimum — one of the few "wasted work" checks worth adding.
Speaker note: Selection sort and quick sort are this week's two clearest examples of instability — Section 11 shows why.
Speaker note: Point them at how many swaps happen per outer-loop iteration.
Speaker note: Contrast with bubble sort, where a badly placed value crawls one cell at a time — up to n(n-1)/2 swaps total.
Speaker note: Section 4 is the sort you already draw on the board — the picture matches exactly how people sort a hand of cards.
Speaker note: You hold a small sorted hand, and slide each new card into the one gap where it belongs.
Speaker note: C's qsort and Java's Arrays.sort both switch to insertion sort once a recursive sub-array shrinks below ~16-32 elements.
Speaker note: The hole moves left with every shift; the key drops in the moment a comparison finds "not greater than".
Speaker note: This is drawn on the board exactly this way every time — the animation matches it element for element.
Speaker note: Normal example: watch the red key box, the "already sorted" brace grow, and the shift arrows one at a time.
Speaker note: The worst case — every single key shifts all the way to the front, one cell at a time.
Speaker note: The bound check `j >= 0` must come first in the && — never read a[-1] to find out.
Speaker note: Small average-case constant makes it genuinely fast for small or nearly-sorted arrays in practice.
Speaker note: Nearly-sorted data — log files, re-sorting after a small update — is exactly insertion sort's sweet spot.
Speaker note: Selection sort gets none of this benefit — its full scan costs the same regardless of how sorted the input already is.
Speaker note: Section 5 asks: what if insertion sort moved badly placed elements most of the way home BEFORE the final pass?
Speaker note: Donald Shell asked exactly this question in 1959 and published the first sort to beat O(n²) in the worst case.
Speaker note: This is a genuinely rare thing in this course: a named person, a named paper, a specific year, still actively researched.
Speaker note: The final gap=1 pass is literally plain insertion sort, but on data that barely needs any shifting left.
Speaker note: Normal example: gap sequence 5, 2, 1 — watch how few shifts the final gap=1 pass needs.
Speaker note: Compare this against Section 4's plain-insertion-sort reverse-sorted example — far fewer total shifts here.
Speaker note: Every line matches plain insertion sort exactly, with "1" replaced by "gap" throughout.
Speaker note: The important idea is the gap itself — the exact optimal sequence is a research question outside this course's scope.
Speaker note: Compare this to the 11 single-cell shifts plain insertion sort would need for the same value.
Speaker note: Large early gaps cover far more ground per shift — that is the entire mechanism behind shell sort's speed.
Speaker note: Section 6 introduces divide and conquer: split, solve each half the same way, combine — the first O(n log n) guarantee today.
Speaker note: Combining two already-sorted halves is cheap — the only remaining question is how to sort each half.
Speaker note: 1945 predates almost every other named algorithm this week — merge sort is genuinely one of the oldest.
Speaker note: This holds in every case — best, average, worst — the only algorithm today with that guarantee.
Speaker note: That O(n) extra memory is the one real cost of merge sort's unconditional guarantee.
Speaker note: The animation draws the recursion literally — one row per depth, split going down, merge continuing further down.
Speaker note: Normal example: watch the split rows (braces only, no value changes), then the merge rows building the sorted result.
Speaker note: Every split and every merge still runs in full — merge sort's guarantee is unconditional, unlike bubble sort's early exit.
Speaker note: `<=` (not `<`) always prefers the left run on a tie — this single choice is what makes merge sort stable.
Speaker note: `lo + (hi-lo)/2`, not `(lo+hi)/2` — the form that stays correct even near integer overflow.
Speaker note: Bottom-up can never overflow a call stack, no matter how large n is — a real practical advantage.
Speaker note: Normal example: watch the width label double each round — width=1, 2, 4, 8 — with no recursion anywhere.
Speaker note: Every round is perfectly even here — compare against the "hard" example, where the last pair each round is partial.
Speaker note: The `min(mid+width, n)` clamp handles both power-of-two and uneven array sizes with no special-casing.
Speaker note: Heap sort (Week 4) shares this O(n log n)-always guarantee, but needs no extra memory — merge sort trades memory for stability.
Speaker note: Give them a moment before revealing — both answers are genuinely practical, not just theoretical.
Speaker note: Production sort libraries do exactly this second optimization — recursive structure makes it a natural fit.
Speaker note: Section 7 asks: can a sort guarantee O(n log n) on average AND sort in place, with no extra array?
Speaker note: Tony Hoare invented exactly that in 1959-1960, and it remains one of the most-used sorts in real software today.
Speaker note: Hoare was 26, a visiting researcher on a machine-translation project — quicksort was almost a side project.
Speaker note: Once both sides are recursively sorted, the whole range is sorted — everything on the left is already <= everything on the right.
Speaker note: The difference is not cosmetic — it changes the recursive call boundaries, a classic source of off-by-one bugs.
Speaker note: The pivot's final position is guaranteed by construction — this is what makes Lomuto's recursion lo,p-1 / p+1,hi correct.
Speaker note: Normal example: watch the pivot (red box), the i boundary, and the pivot's final swap into place.
Speaker note: The classic trap — every partition splits n-1 against 0, the worst possible split. Section 7's worst-case slides return to this.
Speaker note: The final three lines place the pivot into its guaranteed final position, i+1.
Speaker note: p-1 and p+1 both exclude the pivot itself, which is correct because Lomuto guarantees it sits exactly at p.
Speaker note: This "not guaranteed" is the single most important fact about Hoare's scheme — it changes the recursion boundaries.
Speaker note: Normal example: watch the two pointers scan inward and swap, and compare the total swap count to Lomuto's.
Speaker note: Even with every value equal to the pivot, the scan still converges correctly — a good invariant check.
Speaker note: Two do-while loops, each guaranteed to stop at or before the pivot's own position on that side.
Speaker note: Note: p, NOT p-1 — the single most common quick sort bug, because Hoare never guarantees the pivot sits at p.
Speaker note: The same three animations you've already seen — Lomuto's already-sorted example was this exact trap.
Speaker note: Same input, three pivot strategies — first, middle, median-of-three — comparisons and depth counted side by side.
Speaker note: On random data with no adversarial structure, all three strategies perform similarly — the trap needs sorted-like input.
Speaker note: 91 vs 31 on the identical input — O(n²) vs O(n log n) is not an abstraction, it is this exact table.
Speaker note: This is a genuine theorem, not a rule of thumb — you will prove it yourself as an exercise.
Speaker note: This single mix-up — p-1 vs p — is the most common bug students write when implementing quick sort from memory.
Speaker note: The answer is entirely about what each scheme actually guarantees about the pivot's final position.
Speaker note: Lomuto's explicit final swap is exactly what makes its p-1/p+1 recursion safe — Hoare has no equivalent guarantee.
Speaker note: Section 8 opens the second half of the week: sorts that never compare two keys against each other at all.
Speaker note: Then you don't need to compare at all — you can simply count how many times each value occurs.
Speaker note: Seward's thesis is one of the earliest documented non-comparison sorting ideas in computing.
Speaker note: The backward scan guarantees that among equal values, the one appearing earlier in the input claims the earlier output slot.
Speaker note: Watch the comparisons counter — it stays at zero the entire time. That is the whole point of a non-comparison sort.
Speaker note: 10 values but maxVal=15 — the O(n+k) cost made visible: count[] must cover every value up to 15.
Speaker note: After this, count[v] means "how many values are <= v" — the last output index that value should occupy.
Speaker note: Backwards is not optional here — it is the entire mechanism that keeps counting sort stable.
Speaker note: The sparse-range example already showed count[] larger than the input itself for k=15, n=10 — imagine k=1,000,000.
Speaker note: The scan processes a[q] first (larger index), so it claims the later slot; a[p] then claims what's left, one slot earlier.
Speaker note: This is exactly the mechanism from the code slide, traced through for two specific tied elements.
Speaker note: Section 9 rescues counting sort's idea for larger integers, by processing one digit at a time instead of the whole range at once.
Speaker note: Run counting sort digit by digit instead of value by value — always 10 buckets, no matter how large the numbers are.
Speaker note: This is one of the oldest ideas in this entire course — punched-card sorting predates electronic computing by decades.
Speaker note: A stable pass preserves every earlier, less-significant digit's ordering — that composability is the whole algorithm.
Speaker note: Normal example: 3-digit values, 3 passes — watch the array reorder pass by pass, place=1, 10, 100.
Speaker note: Only one pass ever runs — the loop condition naturally stops once every value fits in one digit.
Speaker note: get_digit(5, 100) correctly returns 0 — shorter numbers act as if left-padded with invisible zeros.
Speaker note: This is literally counting sort's exact two-phase structure (Section 8), just keyed on one digit instead of the whole value.
Speaker note: Unlike most other contexts, stability here is not a nicety — it is load-bearing for correctness itself.
Speaker note: The answer is entirely about what each pass can and cannot assume about the digits it has not processed yet.
Speaker note: MSD-first radix sort exists too, but needs a different, recursive structure to work — outside this week's scope.
Speaker note: Section 10 generalizes counting sort: instead of one bucket per value, one bucket per RANGE of values.
Speaker note: If values are spread evenly, each bucket holds only a handful of elements — cheap to finish sorting locally.
Speaker note: Unlike Seward (counting sort) or Hollerith (radix sort), bucket sort is usually presented without a specific attribution.
Speaker note: Bucket b's values are all smaller than bucket b+1's, by construction — concatenation alone finishes the sort.
Speaker note: Normal example: watch values distribute into 10 buckets, then each small bucket get insertion-sorted.
Speaker note: The worst case — every value collides into one bucket, degrading to plain insertion sort on the whole array.
Speaker note: With max_val=99 and 10 buckets, b is literally the tens digit — a clean, easy-to-explain mapping.
Speaker note: Bucket sort's O(n) promise is entirely conditional on the input actually being evenly spread — there is no way to detect this from inside the algorithm.
Speaker note: The key word is "range" versus "single value" — think about what could still be out of order within a bucket.
Speaker note: This is exactly why bucket sort can handle floating-point values in its general form, unlike counting sort's per-value counting.
Speaker note: Section 11 stops defining stability in words and shows it happening, on the same input, with two named algorithms.
Speaker note: Yes — and this is exactly what today's dedicated stability animation does, live, with tagged records.
Speaker note: The tag is a stand-in for "which physical record this was" — imagine a student name, sorted by grade.
Speaker note: Watch the 5a, 5b, 5c group specifically — stable keeps them in order, unstable does not.
Speaker note: The most extreme case — a fully stable sort must reproduce the ENTIRE input order unchanged.
Speaker note: Instability only has something to act on when a swap actually crosses a tied element — sorted input never triggers that.
Speaker note: Radix sort's stability is not optional — Section 9 showed it is required for correctness, not just a nice-to-have.
Speaker note: The trick generalizes to any comparison-based sort, not just selection sort specifically.
Speaker note: This costs extra memory to track indices, but works universally — a good trick to know even if today's sorts don't need it.
Speaker note: Section 12 stops trusting Big-O's hidden constants and just runs five algorithms on the same input, counting exactly.
Speaker note: Five algorithms, one identical input each time, comparisons and writes counted through the same two primitives.
Speaker note: No algorithm here is re-taught — each already has its own dedicated animation. This is purely a side-by-side measurement.
Speaker note: Normal example: watch each row reveal its comparisons/writes tally as its "running..." highlight resolves.
Speaker note: The whole week's lesson in one animation: bubble wins by a landslide, quick (Lomuto) has its worst possible day.
Speaker note: The exact same 66-comparison worst case from Section 7's quick sort slides, now sitting right next to bubble's 11.
Speaker note: This single sentence is the entire justification for teaching eleven different sorting algorithms instead of one "best" one.
Speaker note: Point them back at Section 4's self-check about why insertion sort's cost tracks how far out of place elements are.
Speaker note: Nearly-sorted data is insertion sort's best case in practice, but not selection sort's — a direct callback to Section 4.5.
Speaker note: Section 13 turns everything today into a single practical question: given what you know about your data, which sort?
Speaker note: This table continues over the next two slides — read the full version in this week's notes for the complete nine-row table.
Speaker note: "Memory OK" versus "in place" is the single biggest fork in this whole table — merge sort or quick sort, rarely both matter equally.
Speaker note: These four rows are this week's second half in one glance — the non-comparison sorts, chosen by what you know about the keys.
Speaker note: Knowing all eleven well enough to recognize which situation you're in — that is this week's real, transferable skill.
Speaker note: Eleven algorithms, four families, one underlying question each time: what do you know, and what can you afford?
Speaker note: If you remember one thing from today, make it this: measure, don't assume, and know which situation you are actually in.
Speaker note: Bottom-up merge sort's "merge sorted runs" mechanism becomes the literal foundation for sorting data that lives on disk.
Speaker note: Full notes, all fourteen animations, and every program are in this week's lecture notes — thank you.