Chapter 9 — Medians and Order Statistics

Native fourth-edition chapter guide.

Current source

This guide sources fourth-edition §9.1–§9.3 from the native section modules under CLRSLean.FourthEdition.Chapter_09. Declarations retain the CLRS.Chapter09 namespace; the legacy import CLRSLean.Chapter_09 and its Section_09_* modules forward to these sources during the compatibility period.

Chapter 9 is structurally represented by Sections 9.1--9.3. Section 9.1 is complete for the simultaneous pairwise minimum/maximum algorithm and the CLRS 3 * floor(n / 2) comparison bound. Sections 9.2 and 9.3 are complete for the advertised functional and comparison-cost models: RANDOMIZED-SELECT has a schedule-driven path cost, fresh per-call uniform choices, a bridge to the CLRS larger-side majorizer, and expected partition-work cost at most 4 * c * n; recursive median-of-medians SELECT has an end-to-end cost at most 100n.

Sections

• 9.1 proves simultaneous minimum/maximum correctness and the pairwise comparison bound.

• 9.2 proves duplicate-aware rank selection, pivot-style SELECT correctness, schedule-cost erasure, and the fresh-choice randomized expected-cost bridge.

• 9.3 proves recursive median-of-medians SELECT correctness and its complete worst-case comparison bound.

Closure interface

The chapter's main public results are CLRS.Chapter09.minMax?_correct, CLRS.Chapter09.minMax?_comparisons_le, CLRS.Chapter09.randomizedSelectCostWithSchedule_rankCorrect, CLRS.Chapter09.randomizedSelectExpectedCostFuel_succ, CLRS.Chapter09.randomizedSelectExpectedCost_le_randSelectExpectedCost, CLRS.Chapter09.randomizedSelectExpectedCost_linear_bound, CLRS.Chapter09.recursiveMedianOfMediansSelect?_correct, and CLRS.Chapter09.recursiveMedianOfMediansComparisonCost_linear_bound. The proof map records the supporting theorem inventory.

Completion boundary

The chapter is complete for pure functional correctness and CLRS comparison costs. The RANDOMIZED-SELECT metric charges only c * currentLength; it does not charge the internal specification implementation of selectByRank?, random-number generation, list primitives, or RAM operations, and it does not identify the nested process with a flat distribution on variable-length schedules. Mutable arrays, in-place partitioning, a concrete RNG, and hardware-level accounting are later implementation refinements and do not reopen this theorem boundary.

See docs/clrs-fourth-edition-map.csv for the section-level mapping and docs/migrations/clrs4.md for compatibility and deprecation policy.