45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T489,Understanding *why* radix sort works—not just *that* it works—requires examining the mathematical invariants that guarantee correctness. **Theorem (LSD Radix Sort Correctness):** Given an array of numbers where each number has at most d digits, LSD radix sort using a stable sort at each digit position produces a correctly sorted array. **Proof by induction on the number of passes:** *Base case (k=1):* After one pass (sorting by the 1s digit), the array is correctly sorted if we only consider the 1s digit. All numbers ending in 0 precede those ending in 1, etc. *Inductive step:* Assume after k passes, the array is correctly sorted with respect to the k least significant digits. Consider what happens in pass k+1 (sorting by digit position k+1): - Numbers with different digits at position k+1 are correctly ordered by that digit - Numbers with the *same* digit at position k+1 maintain their relative order from before this pass (by stability) - By the inductive hypothesis, that relative order was correct for the k-digit suffix Therefore, after pass k+1, the array is correctly sorted with respect to the (k+1) least significant digits. ∎64:T503,def lsd_radix_sort(arr): """ LSD Radix Sort for 32-bit non-negative integers. Uses base 256 (8 bits per digit) for efficiency. This means 4 passes for 32-bit integers (32 / 8 = 4). """ if len(arr) <= 1: return arr RADIX = 256 # 2^8, process 8 bits at a time MASK = RADIX - 1 # 0xFF, used for extracting 8 bits # For 32-bit integers, we need 4 passes (0, 8, 16, 24 bit positions) for shift in range(0, 32, 8): # Count occurrences of each digit count = [0] * RADIX for num in arr: digit = (num >> shift) & MASK count[digit] += 1 # Convert counts to cumulative positions for i in range(1, RADIX): count[i] += count[i - 1] # Build output array (traverse backwards for stability) output = [0] * len(arr) for i in range(len(arr) - 1, -1, -1): digit = (arr[i] >> shift) & MASK count[digit] -= 1 output[count[digit]] = arr[i] arr = output # Use output as input for next pass return arr # Example usage with detailed trace numbers = [329, 457, 657, 839, 436, 720, 355] print(f"Original: {numbers}") print(f"Sorted: {lsd_radix_sort(numbers)}")65:Tc29,INITIAL ARRAY: [170, 045, 075, 090, 002, 024, 802, 066] ═══════════════════════════════════════════════════════════════════ PASS 1: Sort by 1s digit (rightmost) ═══════════════════════════════════════════════════════════════════ Number: 170 045 075 090 002 024 802 066 1s digit: 0 5 5 0 2 4 2 6 Buckets after distribution: Digit 0: [170, 090] Digit 2: [002, 802] Digit 4: [024] Digit 5: [045, 075] Digit 6: [066] After Pass 1: [170, 090, 002, 802, 024, 045, 075, 066] │ │ │ │ │ │ │ │ 0s 0s 2s 2s 4s 5s 5s 6s ═══════════════════════════════════════════════════════════════════ PASS 2: Sort by 10s digit ═══════════════════════════════════════════════════════════════════ Input: [170, 090, 002, 802, 024, 045, 075, 066] 10s digit: 7 9 0 0 2 4 7 6 Buckets after distribution: Digit 0: [002, 802] ← Note: 002 before 802 (stable from Pass 1!) Digit 2: [024] Digit 4: [045] Digit 6: [066] Digit 7: [170, 075] ← Note: 170 before 075 (stable from Pass 1!) Digit 9: [090] After Pass 2: [002, 802, 024, 045, 066, 170, 075, 090] │ │ │ │ │ │ │ │ 0x 0x 2x 4x 6x 7x 7x 9x ═══════════════════════════════════════════════════════════════════ PASS 3: Sort by 100s digit (leftmost) ═══════════════════════════════════════════════════════════════════ Input: [002, 802, 024, 045, 066, 170, 075, 090] 100s digit: 0 8 0 0 0 1 0 0 Buckets after distribution: Digit 0: [002, 024, 045, 066, 075, 090] ← All preserved in stable order! Digit 1: [170] Digit 8: [802] FINAL: [002, 024, 045, 066, 075, 090, 170, 802] ✓ SORTED! ═══════════════════════════════════════════════════════════════════ KEY INSIGHT: The stable sort at each pass preserved the ordering from previous passes. After Pass 1, 002 was before 802 (2 < 2, but 002 came first originally). This order was maintained through Pass 2 and Pass 3 because they have the same 10s digit (0) and same 100s digit (0/8).43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792298829139,"state":{"data":{"json":{"id":"seed_c3751d59fe84cfaa5ea26b2debbd2b7a","slug":"radix-sort","category":"Data Structures & Algorithms","topic":"Radix Sort","title":"Radix Sort — Digit-Based Sorting","description":"Master the art of non-comparison sorting through radix sort. Learn how processing numbers digit-by-digit achieves linear time complexity, understand the LSD and MSD variants, and discover when this powerful technique outperforms traditional comparison-based algorithms.","difficulty":"INTERMEDIATE","estimatedMinutes":50,"pages":[{"id":"seed_51fff7023e79f88cd9a7f33f04f9eaf8","title":"Sorting by Digits (LSD or MSD)","order":0,"content":[{"id":"opening-hook","title":"Beyond Comparison: A Different Way to Sort","content":[{"data":{"content":"Imagine you're a postal worker in a large sorting facility, tasked with organizing thousands of letters by their ZIP codes. You could compare each pair of letters and gradually build a sorted pile—but that's not how postal services actually work. Instead, they use **sorting bins**: first separating letters by the first digit of the ZIP code, then by the second digit, and so on.\n\nThis intuitive approach—**sorting by individual digits rather than comparing complete values**—is the fundamental insight behind **radix sort**, one of the most elegant and powerful sorting algorithms ever devised. While comparison-based algorithms like merge sort and quicksort are bound by the O(n log n) lower bound, radix sort sidesteps this limitation entirely by exploiting the **structure of the data** rather than just comparing values."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will deeply understand: (1) How radix sort processes data digit-by-digit to achieve sorting, (2) The critical distinction between Least Significant Digit (LSD) and Most Significant Digit (MSD) approaches, (3) Why processing order matters and how it affects correctness, (4) The mathematical invariants that guarantee radix sort produces correctly sorted output, and (5) How to trace through radix sort execution on real examples.","variant":"info"},"type":"callout"}]},{"id":"fundamental-insight","title":"The Fundamental Insight: Numbers as Sequences","content":[{"data":{"content":"To understand radix sort, we must first shift our perspective on what numbers actually *are*. When we write the number **4271**, we typically think of it as a single atomic value—*four thousand two hundred seventy-one*. But this number is also a **sequence of symbols**: `[4, 2, 7, 1]`, where each symbol comes from a finite alphabet (digits 0-9).\n\n**The key insight:** If we can sort numbers by looking at one digit position at a time—and do so in a way that respects previous sorting decisions—we can sort the entire collection without ever directly comparing two complete numbers.\n\nThis is fundamentally different from comparison-based sorting:"},"type":"text"},{"data":{"rows":[["Core operation","Compare two complete values","Group by individual digits"],["Information per step","Binary (less than or greater)","k-way (digit value 0 to k-1)"],["Lower bound","Ω(n log n) comparisons","No comparison lower bound applies"],["Key insight","Total ordering from pairwise comparisons","Positional notation encodes magnitude"],["Applicable to","Any comparable elements","Elements with positional structure"]],"caption":"Paradigm Comparison: Comparison-Based vs Digit-Based Sorting","headers":["Aspect","Comparison-Based (e.g., Quicksort)","Digit-Based (Radix Sort)"]},"type":"table"},{"data":{"content":"**Why does positional notation matter?**\n\nIn our decimal system, the position of a digit determines its contribution to the value:\n\n```\n4271 = 4×10³ + 2×10² + 7×10¹ + 1×10⁰\n = 4000 + 200 + 70 + 1\n```\n\nCritically, the **leftmost digits contribute more to the value** than rightmost digits. This means:\n- If two numbers differ in their leftmost digit, we know their relative order without examining other digits\n- If two numbers share the same leftmost digit, their relative order depends on subsequent digits\n\nRadix sort exploits this positional structure systematically, processing digits in a specific order to ensure correctness."},"type":"text"},{"data":{"icon":"Info","title":"The Radix Concept","content":"The term **radix** refers to the base of a numeral system. For decimal numbers, the radix is 10 (digits 0-9). For binary, the radix is 2 (bits 0-1). For hexadecimal, the radix is 16 (0-9 and A-F). Radix sort works with any radix, and the choice of radix significantly impacts performance—a trade-off we'll explore in detail.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"lsd-vs-msd","title":"The Two Fundamental Approaches: LSD and MSD","content":[{"data":{"content":"Given that numbers are sequences of digits, a natural question arises: **in what order should we process the digits?** There are two fundamental approaches, each with distinct characteristics:\n\n1. **Least Significant Digit First (LSD Radix Sort)**: Start from the rightmost digit and work toward the leftmost\n2. **Most Significant Digit First (MSD Radix Sort)**: Start from the leftmost digit and work toward the rightmost\n\nRemarkably, both approaches can produce correct sorted output—but they work in fundamentally different ways and have different properties."},"type":"text"},{"data":{"left":[{"data":{"items":["**Process order**: Rightmost → Leftmost","**Sorting strategy**: Sort entire array by each digit position, proceeding through all positions","**Stability requirement**: MUST be stable at each pass","**Recursion**: Not required—purely iterative","**Memory pattern**: Consistent across all passes","**Variable-length strings**: Requires padding"],"title":{"icon":"ArrowRight","text":"LSD Radix Sort (Right to Left)","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Process order**: Leftmost → Rightmost","**Sorting strategy**: Partition by first digit, then recursively sort each partition","**Stability requirement**: Stable if implemented carefully","**Recursion**: Typically recursive or stack-based","**Memory pattern**: Can vary with partition sizes","**Variable-length strings**: Natural fit"],"title":{"icon":"ArrowLeft","text":"MSD Radix Sort (Left to Right)","type":"icon","color":"secondary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**The stability imperative for LSD:**\n\nLSD radix sort has a crucial requirement that MSD does not: **each pass must use a stable sorting algorithm**. A sorting algorithm is *stable* if it preserves the relative order of elements with equal keys.\n\nWhy does LSD require stability? Consider what happens after multiple passes:\n\n1. After sorting by the 1s digit, all numbers ending in 0 come first, then those ending in 1, etc.\n2. When we then sort by the 10s digit, numbers with the same 10s digit must remain in their order from step 1\n3. This ensures that 23 comes before 25 (same 10s digit, but 3 < 5 in 1s digit, established in step 1)\n\nWithout stability, earlier sorting decisions would be destroyed by later passes, producing incorrect results."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Critical: Stability in LSD Radix Sort","content":"Using an unstable sort (like standard quicksort) as the subroutine for LSD radix sort will produce INCORRECT results. The algorithm's correctness depends entirely on each pass preserving the relative order established by previous passes. Counting sort is the typical choice because it is naturally stable and has O(n + k) complexity.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"lsd-detailed","title":"LSD Radix Sort: The Iterative Approach","content":[{"data":{"content":"LSD radix sort is the more common variant, particularly for fixed-length integer sorting. Its elegance lies in its simplicity: perform d passes (one for each digit position), using a stable sort for each pass.\n\n**Algorithm Overview:**\n\n```\nLSD_RADIX_SORT(array, d):\n for digit_position = 0 to d-1: // 0 is rightmost\n STABLE_SORT(array by digit at position digit_position)\n return array\n```\n\nLet's trace through a complete example to build deep intuition."},"type":"text"},{"data":{"content":"**Comprehensive Example:**\n\nConsider sorting the following 3-digit numbers:\n\n```\nInitial array: [329, 457, 657, 839, 436, 720, 355]\n```\n\n**Pass 1: Sort by 1s digit (rightmost)**\n\nWe extract the 1s digit of each number and group accordingly:\n\n```\n329 → digit 9\n457 → digit 7\n657 → digit 7\n839 → digit 9\n436 → digit 6\n720 → digit 0\n355 → digit 5\n```\n\nAfter stable sorting by this digit:\n\n```\n[720, 355, 436, 457, 657, 329, 839]\n 0 5 6 7 7 9 9\n```\n\nNote: 457 appears before 657 (both have digit 7), preserving their original relative order. Similarly, 329 appears before 839 (both have digit 9)."},"type":"text"},{"data":{"content":"**Pass 2: Sort by 10s digit**\n\nNow we sort by the 10s digit, maintaining the order from Pass 1:\n\n```\n720 → digit 2\n355 → digit 5\n436 → digit 3\n457 → digit 5\n657 → digit 5\n329 → digit 2\n839 → digit 3\n```\n\nAfter stable sorting by this digit:\n\n```\n[720, 329, 436, 839, 355, 457, 657]\n 2 2 3 3 5 5 5\n```\n\nCritical observation: Among numbers with 10s digit 2, 720 comes before 329. WHY? Because in Pass 1, 720 (ending in 0) was placed before 329 (ending in 9). The stable sort **preserved this relative order**.\n\nSimilarly, 355 < 457 < 657 because their 1s digits (5, 7, 7) were established in Pass 1, and among 457 and 657 (same 1s digit), their original order was preserved."},"type":"text"},{"data":{"content":"**Pass 3: Sort by 100s digit (leftmost)**\n\nFinal pass sorts by the most significant digit:\n\n```\n720 → digit 7\n329 → digit 3\n436 → digit 4\n839 → digit 8\n355 → digit 3\n457 → digit 4\n657 → digit 6\n```\n\nAfter stable sorting:\n\n```\n[329, 355, 436, 457, 657, 720, 839]\n 3 3 4 4 6 7 8\n```\n\nThe array is now completely sorted!\n\nNotice that 329 < 355 (same 100s digit, but 29 < 55 established by earlier passes) and 436 < 457 (same 100s digit, but 36 < 57). The **cumulative effect of stable sorting at each position** builds up the correct total ordering."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Inductive Invariant","content":"After k passes of LSD radix sort, the array is correctly sorted with respect to the k least significant digits. This invariant is maintained by stability: when sorting by digit k+1, elements with equal (k+1)th digits retain their order, which was correct for the k-digit suffix. After d passes, the entire d-digit numbers are correctly sorted.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"msd-detailed","title":"MSD Radix Sort: The Recursive Approach","content":[{"data":{"content":"MSD radix sort works in the opposite direction, processing from the most significant digit first. This approach is more similar to how a human might sort: first group by the leading digit, then within each group, sort by the next digit, and so on.\n\n**Algorithm Overview:**\n\n```\nMSD_RADIX_SORT(array, digit_position, start, end):\n if start >= end or digit_position > max_digits:\n return\n \n // Partition array[start:end] into buckets by current digit\n buckets = PARTITION_BY_DIGIT(array, start, end, digit_position)\n \n // Recursively sort each bucket\n for each bucket in buckets:\n MSD_RADIX_SORT(bucket, digit_position + 1, bucket.start, bucket.end)\n```"},"type":"text"},{"data":{"content":"**Example: MSD Radix Sort in Action**\n\n```\nInitial array: [329, 457, 657, 839, 436, 720, 355]\n```\n\n**Pass 1: Partition by 100s digit (leftmost)**\n\n```\nDigit 3: [329, 355]\nDigit 4: [457, 436]\nDigit 6: [657]\nDigit 7: [720]\nDigit 8: [839]\n```\n\n**Pass 2: Recursively sort each bucket by 10s digit**\n\nBucket [329, 355] → sorted by 10s digit:\n- 329 has 10s digit 2\n- 355 has 10s digit 5\n- Result: [329, 355] ✓\n\nBucket [457, 436] → sorted by 10s digit:\n- 457 has 10s digit 5\n- 436 has 10s digit 3\n- Result: [436, 457] ✓\n\nSingle-element buckets [657], [720], [839] are already sorted.\n\n**Final result after concatenation:**\n```\n[329, 355, 436, 457, 657, 720, 839] ✓\n```"},"type":"text"},{"data":{"rows":[["Processing order","Right to left (1s → 10s → 100s...)","Left to right (100s → 10s → 1s...)"],["Algorithm structure","Iterative: d sequential passes","Recursive: partition then recurse"],["Bucket handling","All elements in single pass","Separate recursion per bucket"],["Early termination","Always processes all d digits","Can stop when buckets are single elements"],["Stability requirement","Critical—correctness depends on it","Optional—recursion handles subproblems"],["Cache behavior","Consistent—same pattern each pass","Variable—depends on bucket sizes"],["Variable-length keys","Requires padding to max length","Natural handling—shorter keys end recursion early"],["Parallelization","Each pass is inherently sequential","Independent buckets can parallelize"]],"caption":"LSD vs MSD Radix Sort: Detailed Comparison","headers":["Characteristic","LSD Radix Sort","MSD Radix Sort"]},"type":"table"},{"data":{"content":"**When to choose MSD over LSD:**\n\n1. **Variable-length strings**: MSD naturally handles strings of different lengths. \"cat\" and \"category\" can be sorted without padding because once we reach the end of \"cat\", it's placed before any longer string sharing that prefix.\n\n2. **Partially sorted output needed**: MSD can provide lazy evaluation—you can get the smallest k elements without fully sorting the array.\n\n3. **High-entropy leading digits**: When the most significant digits effectively separate the data into small buckets, MSD can terminate early.\n\n4. **Parallelizable workloads**: Independent buckets after the first pass can be sorted in parallel."},"type":"text"},{"data":{"icon":"Info","title":"MSD and String Sorting","content":"MSD radix sort is particularly elegant for string sorting, where it's often called \"multikey quicksort\" or \"three-way radix quicksort\" when combined with three-way partitioning. For string-heavy applications like sorting dictionaries, genomic sequences, or URL databases, MSD variants often outperform generic comparison sorts.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"correctness-proof","title":"The Mathematics of Correctness","content":[{"data":{"content":"$63"},"type":"text"},{"data":{"code":"INVARIANT: After processing digits at positions 0, 1, 2, ..., k-1 (right to left),\n for all pairs of numbers (a, b) where a appears before b in the array:\n\n Either:\n 1. The k-digit suffix of a is less than the k-digit suffix of b, OR\n 2. The k-digit suffixes are equal (their relative order doesn't matter yet)\n\nCONSEQUENCE: When k = d (number of digits), the \"suffix\" is the entire number,\n so condition 1 implies a < b, meaning the array is sorted.","title":"Formal Invariant Statement","fileName":"invariant.md","languageLabel":"Mathematical Notation"},"type":"code"},{"data":{"content":"**Why does MSD work differently?**\n\nMSD correctness relies on a different principle: **divide-and-conquer with lexicographic ordering**.\n\n1. After partitioning by the first digit, all numbers starting with 1 come before those starting with 2, etc. This is *globally* correct because the first digit has the highest weight.\n\n2. Within each partition, the first digit is constant. The relative order of numbers *within* a partition depends only on their remaining digits (positions 2 through d).\n\n3. Recursively sorting each partition solves independent subproblems, eventually reaching single elements or examining all digits.\n\nThe key insight: **MSD is correct because higher-order digits dominate lower-order digits in determining value.** Once we partition by digit k, numbers in different partitions have their relative order fixed forever."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Deep Connection","content":"LSD radix sort builds correctness from the bottom up—least significant decisions first, preserved by stability. MSD radix sort builds correctness from the top down—most significant decisions first, independence via recursion. Both exploit the positional structure of numeral representations, just in opposite directions.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"implementation-details","title":"Practical Implementation Considerations","content":[{"data":{"content":"Moving from algorithm description to practical implementation requires addressing several key details:\n\n**Extracting digits efficiently:**\n\nFor base-10 numbers, extracting the digit at position p:\n```\ndigit = (number / 10^p) % 10\n```\n\nFor base-2^k (binary, octal, hexadecimal), use bit manipulation:\n```\ndigit = (number >> (k * p)) & ((1 << k) - 1)\n```\n\nThe second form is significantly faster because division and modulo by powers of 2 are simple bit operations."},"type":"text"},{"data":{"code":"$64","title":"LSD Radix Sort Implementation (Base 256)","fileName":"lsd_radix_sort.py","languageLabel":"Python"},"type":"code"},{"data":{"content":"**Why base 256?**\n\nUsing base 256 (2⁸) instead of base 10 offers multiple advantages:\n\n1. **Fewer passes**: 32-bit integers require only 4 passes in base-256 vs 10 passes in base-10 (for 10-digit numbers)\n2. **Efficient extraction**: Bit shifting and masking are single-cycle operations on modern CPUs\n3. **Cache-friendly counts**: 256-element count arrays fit comfortably in L1 cache\n4. **Power-of-two alignment**: Computer memory and arithmetic are optimized for powers of 2\n\nThe trade-off is a larger count array (256 vs 10 elements), but this is negligible for modern systems."},"type":"text"},{"data":{"rows":[["2","1","32","2","Too many passes—overhead dominates"],["4","2","16","4","Still too many passes"],["16","4","8","16","Reasonable for small datasets"],["256","8","4","256","Optimal for most cases ✓"],["65536","16","2","65536","Count array too large for L1 cache"]],"caption":"Radix Choice Impact on 32-bit Integer Sorting","headers":["Radix","Bits per digit","Number of passes","Count array size","Trade-off"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"Handling Negative Numbers","content":"Standard radix sort assumes non-negative integers. For signed integers, you must either: (1) Separate negatives, sort each group, then concatenate negatives (reversed) with positives, or (2) Flip the sign bit during sorting to treat the most significant bit correctly (negative numbers have sign bit 1, which would otherwise sort them as larger than positives).","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"visualization","title":"Visualizing Radix Sort Execution","content":[{"data":{"content":"A visual trace helps solidify understanding of how LSD radix sort progressively builds the sorted order. Let's trace through sorting `[170, 045, 075, 090, 002, 024, 802, 066]` with base 10:"},"type":"text"},{"data":{"code":"$65","title":"LSD Radix Sort Visual Trace","fileName":"trace.txt","languageLabel":"Text"},"type":"code"},{"data":{"icon":"Sparkles","title":"The Beauty of LSD Radix Sort","content":"Each pass \"locks in\" correct relative order for numbers that share the current digit. By the final pass, ALL relative orders are correct because we've processed all digits. The stability property acts as a \"memory\" carrying forward the decisions made in earlier passes.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: The Power of Digit-Based Sorting","content":[{"data":{"content":"We've explored the fundamental principles of radix sort—a powerful technique that escapes comparison-based sorting's lower bounds by exploiting the structure of positional numeral representations."},"type":"text"},{"data":{"type":"ordered","items":["**Numbers are sequences of digits** — This perspective enables processing one digit position at a time","**LSD processes right-to-left** — Iterative approach requiring stability at each pass to preserve earlier ordering decisions","**MSD processes left-to-right** — Recursive approach that partitions by most significant digit first, with independent subproblems","**Stability is critical for LSD** — Without stable sorting at each pass, earlier ordering decisions would be destroyed","**Correctness comes from invariants** — LSD: 'sorted by k rightmost digits after k passes'; MSD: 'correct relative order established by dominant digits'","**Radix choice affects performance** — Base 256 is typically optimal for 32-bit integers, balancing passes vs cache efficiency"],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nNow that we understand the fundamental mechanism of radix sort—processing digits one position at a time—we'll examine how radix sort uses **counting sort as a subroutine**. This stable, linear-time sorting algorithm is the engine that powers each pass of radix sort, and understanding it deeply reveals why radix sort achieves its remarkable performance characteristics."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand how radix sort processes numbers digit-by-digit, the critical distinction between LSD and MSD approaches, and why stability is essential for LSD correctness. In the next page, we'll examine the counting sort subroutine that enables radix sort's linear-time performance.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_de1ff39663cce624ccbde4777bf86a6e","title":"Using Counting Sort as Subroutine","order":1,"content":null,"isLocked":true},{"id":"seed_d534dff16e4f61779fadf8bc5b458c8b","title":"Time Complexity: O(d × (n + k))","order":2,"content":null,"isLocked":true},{"id":"seed_4401064e50eebe4512151b8722dffe70","title":"When Radix Sort Excels","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792298828845,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"radix-sort"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"radix-sort\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298829139,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298828844,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_c3751d59fe84cfaa5ea26b2debbd2b7a"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_c3751d59fe84cfaa5ea26b2debbd2b7a\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298829139,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298828844,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_de1ff39663cce624ccbde4777bf86a6e"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_de1ff39663cce624ccbde4777bf86a6e\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298829139,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298828844,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_de1ff39663cce624ccbde4777bf86a6e"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_de1ff39663cce624ccbde4777bf86a6e\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298829139,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792298828844,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_de1ff39663cce624ccbde4777bf86a6e"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_de1ff39663cce624ccbde4777bf86a6e\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298829139,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_de1ff39663cce624ccbde4777bf86a6e","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_de1ff39663cce624ccbde4777bf86a6e\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@66"}]},"children":"$L67"}]