Tag
sorting
- Sep 22, 2026 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. algorithms
- Apr 12, 2026 Convex Hulls by Monotone Chain How a lexicographic sort followed by two stack scans produces the convex hull in O(n log n), and why the collinearity rule decides which points survive. algorithms
- Feb 2, 2026 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. algorithms
- Oct 14, 2025 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. algorithms
- Aug 8, 2025 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. algorithms
- Jul 2, 2025 Sort-Based and Hash-Based Shuffle Implementations Two ways to build the map-side shuffle output, how each one trades sort CPU for file count, and why the file count grows with the reduce task count. data engineering
- Nov 4, 2023 Punched-Card Encoding in Hollerith Tabulating Equipment How a pinned card completes a circuit into a mercury cup, what the hole pattern encodes, and why sorting a deck became the way to answer arbitrary questions about census data. computing history