S031 · Sorting — Merge, Quick, and When to Trust the Built-in

Module M03: Data Structures & Algorithms · Session 31 of 130 · Track: SW 🔀

What you'll be able to do after this session

• Explain Sorting to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S027 — Recursion — Call Stack, Base Case, Worked Examples

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · 15 Sorting Algorithms in 6 Minutes — visual/audio comparison of every classic sort; unforgettable feel for speed differences.
• 🎥 Deep dive (30–60 min) · MIT 6.006 Lecture 3: Insertion, Merge Sort — Erik Demaine formally derives O(n log n) and proves correctness.
• 🎥 Hands-on demo (10–20 min) · NeetCode — Merge Sort explained + coded — writes merge sort in Python line-by-line.
• 📖 Canonical article · Python sorted() / list.sort() — Sorting HOW TO — official doc; explains Timsort, keys, stability.
• 📖 Book chapter / tutorial · CLRS Chapter 2 — "Getting Started" (companion notes) — merge sort as the archetype divide-and-conquer.
• 📖 Engineering blog · Timsort — how Python's sort works (Peters, listsort.txt) — the actual algorithm behind list.sort(), straight from the source tree.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Understand the trade-offs so you know when to worry.

Imagine 500 exam papers dumped on your desk in random order. You need them sorted by roll number so you can hand each back. Merge sort is what you'd do with two friends: split the pile in three, everyone sorts their sub-pile, then you zip the three sorted piles together by repeatedly picking the smallest top-card. Quick sort is the "pick a pivot paper, throw everything smaller to your left, larger to your right, then recurse" strategy — messy but fast on average.

The reason sorting is a session on its own — even though every language ships a sort() — is that which algorithm your language chose leaks into your bug reports. Python's list.sort() uses Timsort (a merge-sort variant), so it's stable (equal keys keep their input order) and blazing-fast on partially-sorted data. C++'s std::sort uses introsort (quick-sort → heap-sort fallback), so it's not stable. If you sort employees by department after sorting by name expecting "same department, still alphabetical," Timsort gives it to you for free and introsort silently doesn't.

The forever gotcha: sorted output is deterministic; the sort algorithm's behaviour on equal keys is not — always ask "is my sort stable?" before you chain sorts.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Let's sort [38, 27, 43, 3, 9, 82, 10] with merge sort. The idea: recursively cut in half, sort each half, merge.

Splitting takes log₂(n) levels; merging each level scans all n items → total O(n log n).

Complexity comparison (memorise this table — every interview asks):

Worked quick-sort trace on [7, 2, 1, 8, 6, 3, 5, 4] picking last element as pivot:

• Pivot = 4. Partition → [2,1,3] | 4 | [7,8,6,5]
• Recurse left [2,1,3], pivot = 3 → [2,1] | 3 | []
• Recurse [2,1], pivot = 1 → [] | 1 | [2]
• Right side [7,8,6,5], pivot = 5 → [] | 5 | [7,8,6]
• Continue until every partition is size ≤ 1. Concatenate → [1,2,3,4,5,6,7,8].

Notice quick-sort's worst case: if the input is already sorted and you always pick the last element, every partition is size n-1 → O(n²). That's why real implementations use randomised pivot or median-of-three.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Save as sort_lab.py and run with python3 sort_lab.py:

import random
import time
 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # merge
    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 quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)       # randomised → avoids O(n²)
    lo  = [x for x in arr if x <  pivot]
    eq  = [x for x in arr if x == pivot]
    hi  = [x for x in arr if x >  pivot]
    return quick_sort(lo) + eq + quick_sort(hi)
 
def bench(fn, data, name):
    t = time.perf_counter()
    out = fn(data)
    dt = (time.perf_counter() - t) * 1000
    print(f"{name:15s} {dt:7.2f} ms   sorted? {out == sorted(data)}")
 
if __name__ == "__main__":
    random.seed(42)
    N = 50_000
    data = [random.randint(0, 1_000_000) for _ in range(N)]
    bench(merge_sort,     data.copy(), "merge_sort")
    bench(quick_sort,     data.copy(), "quick_sort")
    bench(sorted,         data.copy(), "sorted() Timsort")
 
    # Stability demo
    people = [("Alice", "Eng"), ("Bob", "Eng"), ("Carol", "HR"), ("Dan", "Eng")]
    by_name = sorted(people, key=lambda p: p[0])
    by_dept = sorted(by_name, key=lambda p: p[1])  # stable → still alphabetical within dept
    print("Stable chain:", by_dept)

Checklist — observe when you run:

1. Timsort (built-in sorted) is 5–20× faster than your hand-rolled Python versions. That's not because Timsort is smarter algorithmically — it's implemented in C.
2. merge_sort and quick_sort both finish; both agree with sorted().
3. The stability demo prints HR people first, then all Eng people still in alphabetical order — that's stability.
4. Increase N to 500_000 and merge_sort will still finish; a naive recursive Python sort on 5M items might hit RecursionError.
5. Remove random.choice and use arr[-1] as pivot, then feed already-sorted input → watch it get slow (or blow the stack).

Try this modification: replace pivot = random.choice(arr) with pivot = arr[len(arr)//2] (median-of-three would be better). Rerun with data = list(range(50_000)) — does quick_sort still finish quickly?

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

You rarely write a sort in production. You call sorted(), ORDER BY, or df.sort_values(). What bites teams is not knowing what the library does.

War story 1 — the un-stable JavaScript sort. Before ES2019, V8's Array.prototype.sort used an unstable quicksort for arrays >10 elements. A dashboard at a fintech I know sorted transactions first by amount, then by date — and produced different orderings depending on browser. Users emailed "your report is broken." The fix was a one-line stable-sort polyfill. Since ES2019 the spec requires stability, but old Node versions and Safari on older iPads still ship the old behaviour.

War story 2 — the O(n²) DoS. Quick-sort with a deterministic pivot (first, last, or middle) is vulnerable to algorithmic complexity attacks: an adversary crafts input that forces the worst case. In 2003, a Perl hash-table attack (Crosby & Wallach) showed the same idea for hash functions; the same trick works on naive quicksort. Every production quicksort you'll see (V8, Rust sort_unstable, C++ std::sort introsort) either randomises the pivot or falls back to heapsort after log(n) bad partitions.

Gotchas top teams handle:

• External sort. When your data doesn't fit in RAM (Spark, MapReduce, Postgres ORDER BY with work_mem overflow) → merge-sort variants that spill to disk. sort -k on Linux does exactly this.
• Sort keys with side effects. In Python, sorted(x, key=slow_fn) calls slow_fn once per element — but sorted(x, key=lambda a: (slow_fn(a), a)) computes it once too. cmp (custom comparator) calls it O(n log n) times. Always prefer key=.
• Locale-aware sort. ["Åke", "Bob"] sorts differently in Swedish vs English. Use locale.strxfrm or ICU collation for user-facing lists.
• Sort followed by dedup on a stream should be heapq.merge + groupby, not sorted(set(x)) which loses order.

The senior-engineer move: always ask "is this sort stable, and does the underlying data structure guarantee it?" before chaining sorts.

(e) Quiz + exercise · 10 min

1. State merge sort's time and space complexity. Which is worse than quicksort's average case, and why do we still use it?
2. What does "stable sort" mean, and give one real bug it prevents.
3. Why is Python's list.sort() faster than a hand-written merge sort in Python, even though both are O(n log n)?
4. Quick-sort's worst case is O(n²). Describe one input that triggers it and one mitigation.
5. When would you deliberately choose insertion sort over merge sort in production code?
6. Stretch (connects to S027 Recursion): Merge sort is defined recursively. Rewrite merge_sort iteratively (bottom-up: merge pairs of size 1, then size 2, then 4…). What's the practical benefit of the iterative version for very large arrays?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Sorting? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S032): Binary Search — the Pattern Behind 100 Problems
• Previous (S030): Graphs — Representation, BFS, DFS, Shortest Path
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.