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

Sorting contracts: the operation and its storage

Learning objective: implement merge, quick and heap-based sorting; reason about stability, worst-case time and allocated storage; then choose a library sort, selection or streamed merge for the actual task.

The runnable examples use integers with ordinary consistent ordering. The main quicksort mutates its list and uses a three-way partition plus a pending stack; it does not call the separate two-way _partition exercise helper. The latter and quickselect can still take quadratic time on equal keys. “Mutates in place” describes the result location, not an O(1) total-space promise. Detailed contracts follow the script; elementary-operation bounds assume constant-cost comparisons and arithmetic. Practice timings are suggestions, not measured guarantees.

Why this session exists

You will usually use a library sort in production. Understanding its stability, worst-case bounds and memory profile still matters when reviewing code or diagnosing a slow ordering step. This session teaches the three foundational sorts, the two production hybrids (TimSort and Introsort), and the ‘which sort should I actually pick?’ decision tree.

You will be able to

• Implement mergesort and quicksort correctly, from memory, in Python.

• Explain stable vs unstable sort and give one case where stability matters.

• State the worst-case and average-case time and space for each sort in the family.

• Explain Python's stable adaptive sorting: detect runs, extend short runs and merge; distinguish the API guarantee from CPython's versioned merge policy.

• Choose the right sort (or non-sort) for a given constraint: memory, latency, streamed data.

Prerequisites

• S027 · Recursion — merge and quick are recursive divide-and-conquer.
• S029 · Heaps — heapsort is heap + repeated pop.
• S023 · Arrays & Strings — the substrate everything sorts.

Optional archived videos

These are the original optional video links, retained for continuity rather than used as technical evidence; titles, duration and playback were not reverified.

• 15 Sorting Algorithms in 6 Minutes — original attribution: Timo Bingmann; compare how algorithms move values.
• Merge Sort · Explained + Coded — original attribution: NeetCode; follow the merge invariant.
• Quicksort — Partitioning Explained — original attribution: MIT OpenCourseWare; contrast value partitioning with positional splitting.

Pre-read · choose a resource, then trace one example

Further reading: TimSort (Wikipedia)

Further reading: Python sorted() + list.sort()

Further reading: Sorting Algorithms Visualised

(a) Intuition · 5 min

Sorting is what you do when your deck of cards is out of order

Split 50 shuffled cards into two piles, sort each pile, then repeatedly take the smaller top card: that is merge sort. Quicksort instead picks a pivot and groups cards below, equal to and above it before sorting the outer groups. Insertion sort keeps a sorted prefix and inserts the next card into its proper place.

Small inputs may hide asymptotic differences. At larger sizes, input order, equal keys, comparison cost, memory and implementation language all affect performance. Merge sort offers a predictable O(n log n) bound and stability; randomized quicksort offers expected O(n log n), but can still do O(n²) work; textbook array heapsort supplies O(n log n) worst-case time with O(1) auxiliary storage. The allocating heap wrapper below is not that in-place implementation.

Python's sort detects ordered runs and merges them stably. An already sorted list needs only linear scanning work, but arbitrary “nearly sorted” input is not a precise O(n) guarantee.

The three tradeoff axes you must know

Every sort is a point in a 3D trade-off space

• Time complexity — expected cost describes a distribution or random choices; worst-case cost matters for adversarial input and tail-latency budgets.

• Space complexity — separately count output allocation, work buffers and recursion/pending stacks. Reserve strict O(1) auxiliary-space claims for implementations that actually meet them.

• Stability — does the sort preserve the relative order of equal-key items? Matters when you sort by one field and want ties broken by original order.

Python's sorted() is stable — this is a feature, not an accident

sorted(items, key=lambda x: x.age) preserves the relative order of items with the same age. That's what lets you chain sorts: sort by name first, then by age — you end up sorted by (age, name) implicitly. In C++'s std::sort (usually Introsort), tie order is not guaranteed by std::sort; use std::stable_sort when it matters. Different language, different default.

Timeline — 70 years of ‘just sort the array’

The historical lesson is the change in design priorities: merge sorted runs; partition around pivots; use a heap for a worst-case fallback; exploit pre-existing order; then defend fast paths against pathological inputs. Shellsort improves insertion sorting by first comparing distant positions. Pattern-defeating quicksort adds bad-partition detection and specialized partitioning rather than a new stability guarantee.

Tim Peters' TimSort design was introduced for Python 2.3 (released in 2003). The saved CPython 3.14 design notes still call it an adaptive stable natural mergesort, but now describe Powersort for merge scheduling. Java's object-array sorting documentation also describes a stable adaptive mergesort; primitive-array overloads use different implementations. These are versioned implementation choices, not proof that every language uses the same sort. The former timeline's universal adoption and “never beats quicksort” claims were not justified. The Python 2.3 release notes document the change; the original TimSort design link is retained as an optional archive reference.

(b) Where sorting does its work · 15 min

The history leaves us with two contrasting ways to divide the work: split by position and merge later, or partition by value before recursing. Following the values through each process makes the time and memory trade-offs easier to explain.

Mergesort — divide, sort each half, merge

Read downward from the unsorted input. The early splits require no comparisons between values; the ordering work happens when pairs of sorted runs meet again.

The final merge consumes two sorted runs, taking the smaller available value each time. Splitting into equal halves keeps the recursion balanced; the merge step is where this array implementation needs its auxiliary storage.

Quicksort — pivot + partition

Quicksort moves that ordering work to the split. Track the pivot, 5: partitioning puts every smaller value on one side and every larger value on the other before either side is sorted.

Once the two sides are sorted, their positions relative to the pivot are already settled—there is no mergesort-style interleaving step. The risk is in the split itself: a pivot near an extreme leaves one large subproblem instead of two balanced ones. That difference explains the worst-case guarantees in the comparison below.

The comparison table you should memorise

Name: Merge sort

Tagline: Guaranteed O(n log n)

• Stable ✅

• O(n) extra memory ❌

• Predictable worst case ✅

• Best when: you need stability or guaranteed performance

Name: Quicksort

Tagline: O(n log n) avg, O(n²) worst

• Unstable ❌

• In-array partition; total stack bound depends on implementation (our pending stack is O(n) worst case)

• Often good locality; relative speed depends on implementation, comparisons and data

• Best when: mutation is allowed and expected-time behavior is acceptable; do not infer a worst-case guarantee from randomness

Name: Heapsort

Tagline: Guaranteed O(n log n)

• Unstable ❌

• In-place ✅

• Cache-unfriendly (jumps around array) ❌

• Best when: you need O(1) extra memory AND worst-case guarantee — rarely picked

Name: Stable adaptive library sorting (Python; Java object arrays)

Tagline: Real-world hybrid

• Stable ✅

• O(n log n) worst case ✅

• O(n) best case on sorted data ✅

• Best when: you need a complete sorted result in Python; use selection or a heap when that is not the actual task

The decision tree — which sort do I actually pick?

Python or Java?

Desc: In Python use sorted() for a new list or list.sort() to mutate the existing list; both are stable. list.sort() may still allocate O(n) temporary storage. In Java choose the relevant Arrays.sort or collection API and read its overload contract: object and primitive sorts differ.

C++?

Desc: C++ std::sort promises O(n log n) comparisons and does not promise stability; introsort is a common implementation. std::stable_sort preserves equivalent-element order. A strict weak ordering is required; algorithms are not specified by a particular pivot rule.

Doing it manually because design review / exercise?

Desc: Merge sort when stable merging and predictable time are priorities; quicksort when in-array partitioning fits, with explicit stack accounting; textbook iterative heapsort when O(1) auxiliary storage and a worst-case bound are essential. Bubble sort is mainly a teaching exercise.

Data > memory?

Desc: External merge sort — sort bounded chunks, spill runs and merge them with a bounded-fan-in heap. Hadoop documents sort/merge phases; not every distributed ordering operation uses one universal algorithm.

Data is small (<50 items)?

Desc: Insertion sort can be competitive for short runs because of low overhead. The crossover is an empirical implementation choice, not a universal 50-item threshold; CPython uses binary insertion to extend short runs.

Only need top-K?

Desc: For 1 ≤ K ≤ n, a size-K heap uses O(n log(K+1)) work and O(K) storage; sorting the selected output costs O(K log K). For K near n, a full library sort may be simpler or faster. See S029.

Where sorting shows up in real systems

Sorting in the wild

Name: Database ORDER BY

Desc: Inspect the query plan: an index, sort, incremental sort, bounded top-N sort or merge of ordered inputs can supply ordering. PostgreSQL 18 tuplesort source describes in-memory sorting and balanced k-way merge of spilled runs; plan and memory budget determine which path is used.

Name: Log aggregation

Desc: Merging N sorted log streams by timestamp is a k-way merge with a heap (S029 pattern), not a re-sort of the concatenation.

Name: MapReduce shuffle stage

Desc: Hadoop partitions mapper output, sorts it and merges fetched runs for reducers. Network, serialization, skew and computation may dominate; a shuffle does not imply one globally ordered result.

Name: TCP reassembly

Desc: A receiver must buffer out-of-order byte ranges and deliver contiguous bytes in sequence-number order. This is an ordering application, not evidence that TCP is implemented with a priority queue or insertion sort.

Name: Auction / bidding systems

Desc: Ad tech auction results sorted by bid amount within a strict latency budget — high-frequency sorting with tight tail latency.

The single most important sorting rule in production Python

Use sorted(items, key=fn) for a per-item key: Python computes the key once per input item, then compares keys. Python 3 has no cmp= keyword; functools.cmp_to_key adapts a legacy negative/zero/positive comparator. It does not repair an inconsistent ordering. Java and JavaScript have different comparator APIs; do not copy Python keyword rules into them.

Comparator consistency and stable multi-key sorting

A key must yield mutually comparable values. A comparator must return zero for equal-order keys, reverse sign when arguments swap, and respect transitivity. Random or stateful comparison results can violate those rules. Floating-point NaN is unordered; filter it or choose an explicit bucket/order policy rather than assuming ordinary numeric sorting provides a total order. Mixed incomparable types can raise TypeError.

For (age, name) order, a tuple key works directly; alternatively stable-sort by the secondary name first and primary age second. Stability preserves input tie order, not alphabetic order unless the input already has it. Stable sorting alone cannot make nondeterministic input tie order reproducible across runs.

These choices depend on more than the average running time. Stability provides a small, observable test of why two sorts with the same headline complexity are not interchangeable.

Myth: "Quicksort is O(n log n) and mergesort is O(n log n), so they're equivalent — pick either."

Truth: Randomized quicksort has expected O(n log n) and O(n²) worst-case work; its partition mutates the array, but the stack consumes storage. Stable array mergesort uses O(n) auxiliary space and O(n log n) worst-case work. Stability, memory, input structure, comparison cost and constants all help choose between them.

Why: Because complexity tables list one number per algorithm and students memorise the row, not the footnotes. The footnotes are the entire content. Stability in particular looks like trivia until you sort a dataset by one key and then another and discover the first sort's ordering was destroyed — at which point "stable" is the only property you care about.

Test the tie order with the original executable example:

rows = [('b', 2), ('a', 1), ('c', 2), ('d', 1)]
 
# sort by value, then by nothing else: stable sort keeps original relative order
print(sorted(rows, key=lambda r: r[1]))
# [('a',1), ('d',1), ('b',2), ('c',2)]  <- a before d, b before c: input order preserved
 
# multi-key sorting by chaining relies ENTIRELY on stability
by_name  = sorted(rows, key=lambda r: r[0])
by_value = sorted(by_name, key=lambda r: r[1])
print(by_value)   # sorted by value, ties broken by name - only works because sort is stable

Question: Why does comparison sorting require Ω(n log n) comparisons in the worst case for arbitrary distinct keys? This is stated as a law, but it is a counting argument you can reconstruct in four steps.

Premise: A sort of n distinct items must be able to produce any of the n! possible orderings, because any of them could be the correct answer.

Because: the algorithm cannot know the input in advance; if some permutation were unreachable, that input would be sorted incorrectly

Premise: A comparison-based algorithm learns about the input only through yes/no comparisons, so its execution is a binary decision tree.

Because: each comparison has exactly two outcomes, branching the algorithm's state in two

Premise: Each distinct permutation must be a distinct leaf of that tree, so the tree needs at least n! leaves.

Because: two different correct answers cannot be produced by the identical sequence of decisions

Premise: A binary tree with n! leaves has height at least log₂(n!), and the worst-case number of comparisons is the tree's height.

Because: a binary tree of height h has at most 2^h leaves, so h ≥ log₂(leaves)

Premise: By Stirling's approximation, log₂(n!) ≈ n log₂n − n·log₂e, which is Θ(n log n).

Because: n! grows super-exponentially, and its logarithm grows as n log n

Conclusion: Therefore Ω(n log n) is not a limit of our cleverness — it is an information-theoretic floor. You need roughly n log n bits of information to identify one permutation out of n!, and each comparison yields at most one bit. And note what this predicts: the bound applies only to comparison-based sorts. Counting and radix sorts use key structure beyond pairwise comparisons. Counting sort costs O(n + K) for an integer range of size K; base-B LSD radix sort costs O(d(n + B)) for d digits and requires stable digit passes. Only when digit count/range and digit operations are suitably bounded are these linear in n. They are options for structured keys, not mandatory winners on every integer dataset.

Name: Split-then-work vs. work-then-split

Picture: Merge sort and quicksort illustrate two divide-and-conquer organizations; heapsort and counting sort show that not every efficient sort has this form. Mergesort splits blindly down the middle (trivial split) and does all the real work combining two sorted halves (expensive merge). Quicksort does all the work up front partitioning around a pivot (expensive split) and then the combine is nothing — the pieces are already in the right regions. That single choice explains everything downstream. A blind split always halves, so mergesort's depth is guaranteed log n. A pivot-based split only halves if the pivot is near the median, so quicksort's depth is a gamble — and a bad pivot on sorted input gives you depth n.

• Mergesort: guaranteed O(n log n), stable, O(n) extra memory, sequential access — which makes merging useful for external sorted runs.

• Quicksort: expected O(n log n) with random pivots, often good locality, in-array partitioning, unstable, and O(n²) worst case even with randomization. Sorted input is bad for particular deterministic pivot rules, not all quicksorts.

• Heapsort: guaranteed O(n log n) and in-place, but unstable and cache-hostile — the safety net, rarely the first choice.

• Many library sorts are hybrids. CPython detects runs and merges them adaptively: one sorted run takes O(n) work; multiple-run costs depend on their number and lengths.

Trigger: Fire this model the moment you see: ORDER BY in a query plan · a Spark shuffle (inspect its partitioning and ordering requirements) · sort_values on a large DataFrame · a merge join · "top K" · a window function that needs an ordered partition · deduplication · any operation whose cost suddenly jumps and whose plan says "sort".

Decision: You must sort a dataset far larger than memory. In-memory sort per chunk then merge, or push the sort into the storage layer?

Name: External merge sort

Gain: bounds working memory by spilling sorted chunks and merging runs. With k active runs the heap uses O(k) entries, plus per-run I/O buffers. Bound fan-in by file-descriptor and memory limits; additional passes trade I/O for bounded memory.

Cost: spilled runs incur writes and rereads; multiple passes add I/O. Network repartitioning is a separate distributed cost. Which phase dominates must be measured.

Pick: the required ordered result exceeds RAM. A distributed global order also needs ordered nonoverlapping partitions and coordinated output traversal.

Name: Sort at write time / keep data pre-sorted

Gain: a matching physical ordering can avoid a read-time sort and improve pruning. Merge joins additionally need compatible keys and placement; pre-sorted files alone do not guarantee no shuffle.

Cost: writes become more expensive and more complex, and the sort key is now a schema decision you cannot cheaply change later — a wrong key is expensive to undo

Pick: repeated reads favor the same key. Clustered order, LSM sorted runs, multidimensional Z-order and partitioning have different guarantees; partitioning or clustering alone is not a global ORDER BY contract.

Name: Avoid the total order — sample, bucket, or approximate

Gain: selection, bounded heaps or quantile sketches avoid materializing a full total order when only ranks or summaries are required. Range partitioning alone does not sort records within each partition; exact distributed selection/deduplication can still require communication.

Cost: define whether the answer is exact, which rank/error guarantee is needed and what communication remains. A bounded heap can produce exact top-K; a sketch usually provides an approximation, not the same output contract.

Pick: the sort was a means to an end — top-K, percentiles or deduplication — rather than the required deliverable itself.

Verdict: first ask why a total order is needed. Top-K, selection and deduplication admit alternatives, but exact distributed answers may still need a shuffle. Sorting at ingest trades additional write/compaction work and a chosen key against repeated query savings; it is not strictly better for every workload.

(c) Hands-on · 25 min

Save as sorting.py. Zero deps beyond stdlib.

"""sorting.py — implementations + benchmarks for the three foundational sorts.
 
Run:  python sorting.py
"""
from __future__ import annotations
import heapq
import random
import time
 
 
# ------------------------------------------------------------------
# 1) Merge sort — the interview classic
# ------------------------------------------------------------------
def merge_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return _merge(left, right)
 
 
def _merge(left: list[int], right: list[int]) -> list[int]:
    out: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out
 
 
# ------------------------------------------------------------------
# 2) Quicksort — three-way in-array partition; randomized expected time
# ------------------------------------------------------------------
def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    pending = [(lo, hi)]
    while pending:
        lo, hi = pending.pop()
        if lo >= hi:
            continue
        pivot = a[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1; i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        pending.extend([(lo, lt - 1), (gt + 1, hi)])
 
def _partition(a: list[int], lo: int, hi: int) -> int:
    # Two-way exercise helper, NOT called by quicksort; randomization is no worst-case bound.
    pivot_idx = random.randint(lo, hi)
    a[pivot_idx], a[hi] = a[hi], a[pivot_idx]
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1
 
 
# ------------------------------------------------------------------
# 3) Heap sort — build heap, repeatedly extract min
# ------------------------------------------------------------------
def heap_sort(a: list[int]) -> list[int]:
    heap = list(a)                   # copy so we don't mutate input
    heapq.heapify(heap)              # O(n)
    return [heapq.heappop(heap) for _ in range(len(heap))]   # n * O(log n) = O(n log n)
 
 
# ------------------------------------------------------------------
# 4) Insertion sort — perfect for small or almost-sorted lists
# ------------------------------------------------------------------
def insertion_sort(a: list[int]) -> list[int]:
    a = list(a)
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a
 
 
# ------------------------------------------------------------------
# 5) External merge — sorted chunks + k-way heap merge
# ------------------------------------------------------------------
def external_merge(chunks: list[list[int]]) -> list[int]:
    """Merge k sorted chunks: O(k + n*log(k+1)) work; materialize n outputs."""
    return list(heapq.merge(*chunks))       # stdlib's k-way merge
 
 
# ------------------------------------------------------------------
# 6) Stability demo — TimSort preserves equal-key order; naive quicksort does not
# ------------------------------------------------------------------
def stability_demo() -> None:
    people = [("Alice", 30), ("Bob", 25), ("Carol", 30), ("Dan", 25), ("Eve", 30)]
    # Sort by age with sorted() — stable, preserves name order within each age group
    by_age_stable = sorted(people, key=lambda p: p[1])
    print("stable  (TimSort):", by_age_stable)
    # No shuffle is performed here; stability preserves the input order of ties.
    print("(if we sorted by NAME first then age, we'd get age-primary, name-secondary sorted)")
 
 
# ------------------------------------------------------------------
# 7) Small observational benchmark on 1,000 random integers
# ------------------------------------------------------------------
def benchmark() -> None:
    n = 1_000
    data = [random.randint(0, 1_000_000) for _ in range(n)]
 
    for name, fn in [
        ("merge_sort",  lambda d: merge_sort(d)),
        ("quicksort",   quicksort),  # the branch below captures the mutated list
        ("heap_sort",   lambda d: heap_sort(d)),
        ("sorted() TimSort", lambda d: sorted(d)),
    ]:
        d = data[:]
        t = time.perf_counter()
        if name == "quicksort":
            quicksort(d)
            result = d
        else:
            result = fn(d)
        dt = time.perf_counter() - t
        assert result == sorted(data)
        print(f"{name:20s} n={n} : {dt*1000:.1f} ms")
 
 
if __name__ == "__main__":
    print("merge_sort [3,1,4,1,5,9,2,6]:", merge_sort([3, 1, 4, 1, 5, 9, 2, 6]))
    a = [3, 1, 4, 1, 5, 9, 2, 6]; quicksort(a); print("quicksort in-place:", a)
    print("heap_sort  [3,1,4,1,5,9,2,6]:", heap_sort([3, 1, 4, 1, 5, 9, 2, 6]))
    print("insertion  [3,1,4,1,5,9,2,6]:", insertion_sort([3, 1, 4, 1, 5, 9, 2, 6]))
    print("external_merge:", external_merge([[1, 4, 7], [2, 5, 8], [3, 6, 9]]))
    stability_demo()
    benchmark()

Anatomy of the script

What each function teaches

Name: merge_sort

Desc: Textbook divide-and-conquer. Recurses into halves, merges. O(n log n) time, O(n) extra memory. Stable.

Name: quicksort + _partition

Desc: The main quicksort groups less/equal/greater keys, then schedules the two outer ranges. Random pivots give expected balance, not a worst-case time bound. _partition is a separate two-way Lomuto helper: on all-equal keys it returns the last index. Median-of-three is a heuristic; introsort adds a depth-triggered worst-case fallback.

Name: heap_sort

Desc: heapify (O(n)) + n pops (O(log n) each) gives O(n log n). This version copies the heap and allocates the result, so it is not an O(1)-auxiliary-space heapsort. Textbook in-place heapsort uses a max-heap in the input array, swaps its root into the suffix and sifts down within the shrinking prefix.

Name: insertion_sort

Desc: Stable when shifts use strict > as here. O(n²) worst-case and O(n) on already-sorted input; this function copies the list, using O(n) extra storage. CPython uses a binary-insertion variant for short runs, not this exact function.

Name: external_merge

Desc: heapq.merge lazily merges already sorted streams. This wrapper accepts materialized chunks and calls list(...), allocating the entire O(n) output. For true external merging, feed bounded buffered iterators and consume the result incrementally; do not wrap it in a list.

Name: stability_demo

Desc: Sorting by age preserves the original relative order of people tied on age. The demonstration names happen to begin in alphabetical order; stability itself does not sort names.

Name: benchmark

Desc: The exact script times 1,000 random integers and verifies each result outside the timed section. It is a toy observation, not a 100,000-item benchmark or a certified 10× speedup; interpreter, hardware and input structure matter.

What to observe when you run it

All four hand-rolled sorts produce the same sorted output on the test input. The stability_demo shows that (Alice, 30), (Carol, 30), (Eve, 30) appear in that order — preserved from the input. Compare observed timings without asserting a ratio: the built-in avoids Python-level sorting loops, but this tiny run is not a controlled performance study. Try sorted, reverse-sorted and equal-key inputs. The adaptive built-in and three-way quicksort handle these differently; equal-key quicksort is linear here, while two-way quickselect can be quadratic.

Goal: Implement quickselect — expected O(n) on distinct keys, with duplicate and worst-case limits

Hint: Partition and keep only the side containing index k. The displayed exercise uses a two-way partition, not the main three-way quicksort. For distinct keys it is expected O(n), worst O(n²); all-equal keys can force O(n²) even with random pivots. NumPy documents introselect with an O(n) worst-case bound; do not identify it with this teaching implementation.

def quickselect(a: list[int], k: int) -> int:
    """Valid 0 <= k < len(a); expected O(n) for distinct keys, O(n^2) worst."""
    import random
    a = list(a)
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        pivot_idx = random.randint(lo, hi)
        a[pivot_idx], a[hi] = a[hi], a[pivot_idx]
        pivot = a[hi]
        i = lo - 1
        for j in range(lo, hi):
            if a[j] <= pivot:
                i += 1
                a[i], a[j] = a[j], a[i]
        a[i + 1], a[hi] = a[hi], a[i + 1]
        p = i + 1
        if p == k:
            return a[p]
        elif p < k:
            lo = p + 1
        else:
            hi = p - 1
    return -1
 
print(quickselect([3, 2, 1, 5, 6, 4], 1))    # 2nd smallest = 2
print(quickselect([3, 2, 1, 5, 6, 4], 4))    # 5th smallest = 5

Exercise answer: with [3, 2, 1, 5, 6, 4], ranks 1 and 4 return 2 and 5. Require an integer k with 0 <= k < len(a); empty input and out-of-range ranks are outside the exercise contract. Its -1 fallthrough is not a reliable validation signal because -1 can be a valid selected value. It copies input (O(n) storage) and partitions repeatedly, not in one pass. Rank n//2 gives the upper median for even n; the conventional numeric median averages the two middle ranks. Two heaps instead support an online median after each insertion.

Exact implementation storage and invariants

• merge_sort: input is not mutated; each merge preserves sorted order and chooses the left item on equality (<=), making it stable. Peak auxiliary list storage is O(n), plus O(log n) frames, though slicing allocates O(n log n) elements cumulatively. Empty and singleton inputs return the original list object; larger inputs return a new list.
• quicksort: before each inner step, [lo, lt) is below the pivot, [lt, i) equals it, (gt, hi] exceeds it and [i, gt] remains unknown. A swap from the high end must re-examine i. The function returns None and mutates only the valid inclusive [lo, hi] range. Its explicit stack removes recursive call-depth failures, but blindly pushing both ranges can retain O(n) pending ranges in a bad pivot sequence. Processing the smaller side first while deferring the larger is a separate O(log n)-stack improvement, not implemented here.
• heap_sort is an allocating O(n)-space wrapper, not stable by contract. insertion_sort is stable but copies O(n) elements. external_merge requires each chunk sorted and materializes O(n) output; the underlying iterator needs O(k) heap entries for k nonempty streams.
• Strict-weak-order comparisons must agree: the integer examples satisfy this. Custom wrappers used to inspect stability must define the operators the specific algorithm calls. Large integers and long strings can make comparison cost nonconstant.

For a practical in-place heapsort exercise, the following complete implementation uses only indices and swaps. At each extraction the maximum of the remaining prefix moves to its final position; the suffix stays sorted and never re-enters the heap.

def heap_sort_inplace(a):
    def sift(root, stop):
        while 2 * root + 1 < stop:
            child = 2 * root + 1
            if child + 1 < stop and a[child] < a[child + 1]:
                child += 1
            if not a[root] < a[child]:
                return
            a[root], a[child] = a[child], a[root]
            root = child
    for root in range(len(a) // 2 - 1, -1, -1):
        sift(root, len(a))
    for stop in range(len(a) - 1, 0, -1):
        a[0], a[stop] = a[stop], a[0]
        sift(0, stop)
 
values = [3, 1, 4, 1, 5]
heap_sort_inplace(values)
assert values == [1, 1, 3, 4, 5]

(d) Production reality · 15 min

Adaptive runs, not universal speedup stories

An input containing two long sorted runs needs little run discovery and one merge, unlike a random permutation with many short runs. That is why adaptive sorting can exploit production structure. CPython's design notes and Java's object-array API support this mechanism; neither justifies a universal 2–5× claim or the old assertion that Java, Swift, Rust and every other platform share one implementation. Compare real workload distributions and memory costs, not language slogans.

Adversarial partitions and latency budgets

McIlroy's 1999 A Killer Adversary for Quicksort constructs a comparison-driven adversary against common quicksort implementations. It is not evidence for the former unsupported 2003 Apache incident narrative. Random pivots help against fixed inputs, but do not make quadratic outcomes impossible; median-of-three alone gives no worst-case bound. Introsort limits bad partition depth and switches to heapsort. Separately enforce input-size, CPU and memory limits when sorting untrusted data; changing the pivot rule does not limit an expensive comparison callback.

Stability versus reproducibility

Suppose two rows tie on user_id. A stable sort preserves whichever of them arrived first. If distributed arrivals change between runs, the output tie order can still change. For reproducible exports, sort by a deterministic complete key such as (user_id, event_time, unique_event_id) or establish a deterministic input tie order. NumPy and pandas APIs have their own stable-sort options and dtype/axis rules; select them explicitly rather than transferring Python's default to another library. This is a worked failure mode, not an attributed company incident.

Where this shows up in the rest of the plan

Root: Sorting is a building block for half of what's coming

Label: S032 · Binary Search

Desc: Requires sorted input. Sort + binary search is a common combo.

Label: S033 · Dynamic Programming

Desc: Weighted interval scheduling sorts jobs by finish time before DP. Ordinary LIS must preserve original sequence order: sorting its input changes the problem. Unweighted activity selection is a classic greedy problem.

Label: S037 · SQL Joins

Desc: Sort-merge join requires appropriately ordered inputs; it can reuse existing compatible order rather than always sorting both tables.

Label: S048 · Log Aggregation

Desc: Merging N sorted log streams by timestamp = external merge with a heap.

Label: S055 · MapReduce / Spark

Desc: Shuffle partitions and transfers records; inspect which stages sort/merge and whether ordering is per partition or global.

Label: Application · A/B testing ranking (not S097, which teaches perceptrons)

Desc: Ranking treatment/control by lift, with tied breaking by name → chained stable sorts.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — answers follow directly

Q: State the time and space complexity of merge, quick, and heap sort.

A: Stable array mergesort uses O(n log n) worst-case work and O(n) auxiliary storage. Randomized quicksort has expected O(n log n) and worst O(n²) work; its stack is implementation-dependent (O(n) worst case for this pending-stack version). Textbook iterative in-place heapsort is O(n log n) worst case and O(1) auxiliary storage, unlike the O(n)-space heap_sort wrapper.

Q: What does ‘stable sort’ mean and when does it matter?

A: Equal-key items retain their relative input order. Matters when you sort by ONE field and want existing order preserved for ties — e.g. sort by age but keep original name order within each age. Enables chained sorts.

Q: Which sorts are stable? Which are not?

A: Conventional left-on-tie mergesort, insertion sort with strict shifts, bubble sort with strict swaps and Python sorting are stable. Conventional quicksort, heapsort and selection sort do not preserve ties. Stability depends on the variant: changing merge <= to < can break it. C++ std::sort does not guarantee stability; use std::stable_sort when needed.

Q: Why is quicksort's worst case O(n²) and how do we defend against it?

A: Repeated extreme pivots leave subproblems of sizes n−1, n−2, …, so the work sums to O(n²). Randomness and median-of-three reduce particular risks but do not remove the worst case. Three-way partition avoids repeatedly recursing over equal keys; introsort adds a depth-budget heapsort fallback (often around 2·log₂ n).

Q: What is TimSort in one paragraph?

A: A stable, adaptive mergesort hybrid. Scans the input for existing runs (ascending or strictly descending), reverses descending runs, extends short runs with insertion sort, then merges them intelligently. O(n) on sorted / reverse-sorted input, O(n log n) worst case. Introduced for Python 2.3; CPython 3.14 uses Powersort to schedule merges. The stable API guarantee is distinct from those implementation details.

Q: You have 100M records that don't fit in memory. How do you sort them?

A: External merge sort: read chunks that DO fit in memory, sort each with an in-memory sort, write sorted chunks to disk. Then use a k-way heap merge (like heapq.merge) to stream them into one sorted output. Bound merge fan-in and output buffering; per-partition ordering is not automatically a global order.

Q: When should you NOT sort?

A: Top-K can use a bounded heap; one rank can use selection (expected linear for suitable quickselect variants, but this two-way exercise is quadratic on some duplicate inputs). Membership can use a set with expected constant lookup. A heap gives the minimum seen so far; emitting a globally sorted unbounded stream needs a completion signal or a valid watermark/bound on future keys.

Q: Why can repeatedly inserting into a sorted Python list cost more than appending all items and sorting once?

A: Each insertion into a sorted list is O(n) (shift). Better: append all items to a list, then sort ONCE → O(n log n). Or maintain a heap or use bisect.insort for online-sorted-with-slow-insert semantics.

Q: What's the difference between key= and cmp= in Python's sorted()?

A: key computes a comparable value from each item ONCE → O(n) key computations. cmp (removed in Python 3) called a comparator O(n log n) times. Use functools.cmp_to_key to convert legacy cmp to key.

Q: Stretch — describe a linear-time sort. What are its constraints?

Stretch: true

A: Counting sort maps bounded integer keys (offset negative minima if needed) to K counts, then emits each key with its multiplicity: O(n + K) time and O(K) counts, plus output. Stable record counting sort needs positions and an output buffer. LSD radix sort performs stable digit passes, costing O(d(n + B)) for d digits in base B. It is O(n) only with suitably bounded d and B; arbitrary-width keys and huge ranges invalidate a blanket linear claim.

Explain-out-loud test

Teach these three, one minute each, no notes:

1. Explain mergesort to a friend using a deck of cards.
2. When would you pick quicksort over mergesort — and vice versa?
3. Why should you almost always just call sorted() instead of implementing anything?

Explain-out-loud answer guide

1. Split the deck by position, recursively sort both halves, then merge their smallest remaining cards. Every level handles n cards and there are O(log n) levels; left-on-tie choice preserves stability.
2. Choose stable merging for its predictable work and tie order when O(n) storage fits. Choose in-array partitioning when mutation is acceptable, but count the stack and state whether randomized expected time is sufficient; for strict O(1) auxiliary storage and a worst-case bound consider iterative heapsort.
3. The library supplies tested ordering behavior, key extraction and optimized loops. Use it for a full sorted result; use a bounded heap or selection when the question asks for less.

What comes next

Next: S032 · Binary Search — Bug-Free Variants

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• Python 3.14 sorting HOWTO — stability, keys, NaN and comparison adapters.
• CPython 3.14 listsort design — adaptive runs, temporary storage and Powersort merge policy.
• Java 25 Arrays and C++ sorting requirements — versioned object/primitive and comparator contracts.
• Princeton merge sort and quicksort — teaching bounds and equal-key partitioning.
• NumPy partition, heapq.merge, PostgreSQL 18 tuplesort source, and Hadoop MapReduce tutorial — selection and bounded merge mechanisms.
• McIlroy, A Killer Adversary for Quicksort — original adversarial comparison construction, 1999.

Primary passages and exact-source finite tests were checked on 2026-10-10; no universal speed ratio, service incident or site-wide approval is inferred.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.