Algorithms · Cluster
Sorting and Selection
Comparison sorts, distribution sorts, and order statistics.
- 01 The Comparison Sorting Lower Bound and What It Actually Counts Why comparison sorts need about n log n comparisons, how the decision-tree and adversary arguments differ, and which cost models the bound leaves out.
- 02 Insertion Sort and the Inversion Count That Predicts Its Runtime How the shift loop makes insertion sort cost exactly n plus the number of inversions, why that adaptivity matters more than the quadratic worst case, and what binary insertion does not fix.
- 03 Merge Sort: Why Stability Survives the Merge and What the Buffer Costs The merge invariant that preserves equal-key order, the three places extra memory is required, and how natural runs turn the algorithm adaptive.
- 04 Quicksort Partition Schemes and the Duplicate-Key Quadratic How Lomuto and Hoare partitioning differ in swap count and branch behaviour, why two-way partitions degrade on equal keys, and what three-way partitioning restores.
- 05 Counting and Radix Sort: Choosing the Pass Count and the Digit Width How stable counting sort works in one linear pass, how LSD radix composes passes, and how digit width trades passes against counter size.
- 06 Comparator Contracts and Why a Bad One Crashes the Sort Strict weak ordering is the precondition every library sort relies on; violating it turns a sort into an out-of-bounds read, and the failure is silent until it is not.
- 07 Quickselect and the Cost of Finding One Element in Place How the selection recursion differs from quicksort, why the expected cost is linear, and which inputs make the linear promise fail.
- 08 Introsort: Bounding Quicksort with a Depth Counter and a Heap How a recursion-depth budget converts quicksort into a worst-case n log n algorithm, and why heapsort is the fallback rather than merge sort.
- 09 Median-of-Medians and the Deterministic Linear Selection Bound Why grouping into fives makes the pivot provably good, how the recurrence resolves to a linear bound, and why the constant keeps it out of hot paths.
- 10 External Sorting: Run Generation, k-Way Merge, and the Fan-In Limit How replacement selection builds long runs from a bounded buffer, how a loser tree merges k runs, and why the merge width is capped by seeks rather than memory.