{"title":"Radix Sort","description":"","content":"Radix Sort sorts numbers without ever comparing two of them directly. It processes one digit position at a time and uses a stable sorting algorithm like Counting Sort to reorder elements at each position. Repeating this across all digit positions produces a fully sorted array.\n\n\n\n\n\nIt runs in O(d * (n + k)) time, where d is the number of digits and k is the radix (10 for decimal). This makes it efficient for large sets of integers or fixed-length strings.\n\nThis chapter covers how Radix Sort works, how it builds on Counting Sort, and when it outperforms comparison-based sorting algorithms.\n\n---\n\n# What Is Radix Sort?\n\nRadix sort is a **non-comparison sorting algorithm** that processes elements one digit (or character) at a time. Instead of asking \"is A greater than B?\", it groups elements by the value of a specific digit position, then repeats for the next position until all positions have been processed.\n\nThe word \"radix\" means \"base\", as in the base of a number system. For decimal numbers, the radix is 10 (digits 0-9). For binary strings, the radix is 2. For lowercase English letters, the radix is 26.\n\n### Two Variants\n\nThere are two ways to process the digit positions:\n\n1. **LSD (Least Significant Digit first):** Start from the rightmost digit and move left. This is the more common variant and the one covered in this chapter. It naturally handles numbers with different digit counts and is easier to implement.\n2. **MSD (Most Significant Digit first):** Start from the leftmost digit and move right. This variant works well for strings and can short-circuit early, but it requires recursion and is more complex to implement.\n\n\n```mermaid\nflowchart LR\n A[\"LSD Radix Sort\"] --> B[\"Sort by ones digit\"]\n B --> C[\"Sort by tens digit\"]\n C --> D[\"Sort by hundreds digit\"]\n D --> E[\"Sorted Array\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#ffa94d,stroke:#000,color:#000\n style E fill:#69db7c,stroke:#000,color:#000\n```\n\n\nEach pass uses a **stable sort** as a subroutine. Stability means that elements with the same digit value retain their relative order from the previous pass. Without stability, sorting by the tens digit would destroy the ordering produced by the ones-digit pass. Counting sort is commonly used as the subroutine because it is stable, runs in O(n + k) time, and works well for small ranges of values (like digits 0-9).\n\n### LSD vs MSD: A Quick Comparison\n\n\n| Aspect | LSD | MSD |\n|--------|-----|-----|\n| **Direction** | Right to left (ones, tens, hundreds, ...) | Left to right (hundreds, tens, ones, ...) |\n| **Implementation** | Iterative, simpler | Recursive, more complex |\n| **Stability** | Naturally stable | Requires care to maintain |\n| **Best for** | Fixed-length integers, same-length strings | Variable-length strings, can short-circuit |\n| **Passes required** | Always d passes (d = max digits) | Can terminate early for some inputs |\n\n\n---\n\n# How It Works\n\nThe LSD radix sort algorithm follows these steps:\n\n1. **Find the maximum value** in the array to determine how many digit positions to process.\n2. **For each digit position** (starting from the least significant), use counting sort to sort the array based on the current digit. The counting sort only looks at one digit of each number, not the entire number.\n3. After processing all digit positions, the array is fully sorted.\n\n\n```mermaid\nflowchart TD\n A[\"Find max value
to get digit count d\"] --> B[\"Set position = 1
(ones digit)\"]\n B --> C[\"Counting sort by
current digit position\"]\n C --> D{\"Processed all
d digits?\"}\n D -- \"No\" --> E[\"Move to next
digit position\"]\n E --> C\n D -- \"Yes\" --> F[\"Array is sorted\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#38d9a9,stroke:#000,color:#000\n style D fill:#ffd43b,stroke:#000,color:#000\n style E fill:#ffa94d,stroke:#000,color:#000\n style F fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Extracting a Digit\n\nThe digit at a given position is isolated with this formula:\n\n\n```shell\ndigit = (number / position) % 10\n```\n\n\nWhere `position` is 1 for the ones digit, 10 for the tens digit, 100 for the hundreds digit, and so on.\n\nFor example, to extract the tens digit of 753:\n\n\n```shell\n(753 / 10) % 10 = 75 % 10 = 5\n```\n\n\n### Why Does LSD Work?\n\nSorting by the least significant digit first produces a correct result because of stability. After sorting by the ones digit, all numbers with the same ones digit are grouped together. Sorting by the tens digit next groups numbers with the same tens digit, and within each group the relative order from the ones-digit pass is preserved. By the time the most significant digit is processed, each pass has refined the ordering, and stability ensures that earlier passes are never undone.\n\nThis is the same effect as sorting a spreadsheet by column C, then by column B, then by column A: the final result is sorted primarily by A, then by B within ties, then by C within further ties.\n\n---\n\n# Code Implementation\n\n### Counting Sort as Subroutine\n\nRadix sort needs a version of counting sort that sorts based on a specific digit position rather than the full value. The `exp` parameter indicates which digit position is being sorted (1 for ones, 10 for tens, 100 for hundreds).\n\n\n```java\npublic class RadixSort {\n\n public static void radixSort(int[] arr) {\n if (arr.length <= 1) return;\n\n int max = arr[0];\n for (int num : arr) {\n if (num > max) max = num;\n }\n\n for (int exp = 1; max / exp > 0; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n }\n\n private static void countingSortByDigit(int[] arr, int exp) {\n int n = arr.length;\n int[] output = new int[n];\n int[] count = new int[10];\n\n // Count occurrences of each digit\n for (int num : arr) {\n int digit = (num / exp) % 10;\n count[digit]++;\n }\n\n // Convert counts to positions\n for (int i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n // Build output array (traverse right to left for stability)\n for (int i = n - 1; i >= 0; i--) {\n int digit = (arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n // Copy output back to arr\n System.arraycopy(output, 0, arr, 0, n);\n }\n\n public static void main(String[] args) {\n int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};\n radixSort(arr);\n System.out.println(java.util.Arrays.toString(arr));\n // Output: [2, 24, 45, 66, 75, 90, 170, 802]\n }\n}\n```\n\n```python\ndef radix_sort(arr):\n if len(arr) <= 1:\n return arr\n\n max_val = max(arr)\n\n exp = 1\n while max_val // exp > 0:\n counting_sort_by_digit(arr, exp)\n exp *= 10\n\n return arr\n\ndef counting_sort_by_digit(arr, exp):\n n = len(arr)\n output = [0] * n\n count = [0] * 10\n\n # Count occurrences of each digit\n for num in arr:\n digit = (num // exp) % 10\n count[digit] += 1\n\n # Convert counts to positions\n for i in range(1, 10):\n count[i] += count[i - 1]\n\n # Build output array (traverse right to left for stability)\n for i in range(n - 1, -1, -1):\n digit = (arr[i] // exp) % 10\n output[count[digit] - 1] = arr[i]\n count[digit] -= 1\n\n # Copy output back to arr\n for i in range(n):\n arr[i] = output[i]\n\nif __name__ == \"__main__\":\n arr = [170, 45, 75, 90, 802, 24, 2, 66]\n radix_sort(arr)\n print(arr)\n # Output: [2, 24, 45, 66, 75, 90, 170, 802]\n```\n\n```cpp\n#include \n#include \n#include \n\nvoid countingSortByDigit(std::vector& arr, int exp) {\n int n = arr.size();\n std::vector output(n);\n int count[10] = {0};\n\n // Count occurrences of each digit\n for (int num : arr) {\n int digit = (num / exp) % 10;\n count[digit]++;\n }\n\n // Convert counts to positions\n for (int i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n // Build output array (traverse right to left for stability)\n for (int i = n - 1; i >= 0; i--) {\n int digit = (arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n // Copy output back to arr\n arr = output;\n}\n\nvoid radixSort(std::vector& arr) {\n if (arr.size() <= 1) return;\n\n int maxVal = *std::max_element(arr.begin(), arr.end());\n\n for (int exp = 1; maxVal / exp > 0; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n}\n\nint main() {\n std::vector arr = {170, 45, 75, 90, 802, 24, 2, 66};\n radixSort(arr);\n for (int num : arr) {\n std::cout << num << \" \";\n }\n // Output: 2 24 45 66 75 90 170 802\n return 0;\n}\n```\n\n```go\npackage main\n\nimport \"fmt\"\n\nfunc radixSort(arr []int) []int {\n\tif len(arr) <= 1 {\n\t\treturn arr\n\t}\n\n\tmaxVal := arr[0]\n\tfor _, num := range arr {\n\t\tif num > maxVal {\n\t\t\tmaxVal = num\n\t\t}\n\t}\n\n\tfor exp := 1; maxVal/exp > 0; exp *= 10 {\n\t\tcountingSortByDigit(arr, exp)\n\t}\n\n\treturn arr\n}\n\nfunc countingSortByDigit(arr []int, exp int) {\n\tn := len(arr)\n\toutput := make([]int, n)\n\tcount := make([]int, 10)\n\n\t// Count occurrences of each digit\n\tfor _, num := range arr {\n\t\tdigit := (num / exp) % 10\n\t\tcount[digit]++\n\t}\n\n\t// Convert counts to positions\n\tfor i := 1; i < 10; i++ {\n\t\tcount[i] += count[i-1]\n\t}\n\n\t// Build output array (traverse right to left for stability)\n\tfor i := n - 1; i >= 0; i-- {\n\t\tdigit := (arr[i] / exp) % 10\n\t\toutput[count[digit]-1] = arr[i]\n\t\tcount[digit]--\n\t}\n\n\t// Copy output back to arr\n\tcopy(arr, output)\n}\n\nfunc main() {\n\tarr := []int{170, 45, 75, 90, 802, 24, 2, 66}\n\tradixSort(arr)\n\tfmt.Println(arr)\n\t// Output: [2 24 45 66 75 90 170 802]\n}\n```\n\n```csharp\nusing System;\n\npublic class RadixSort\n{\n public static void Sort(int[] arr)\n {\n if (arr.Length <= 1) return;\n\n int max = arr[0];\n foreach (int num in arr)\n {\n if (num > max) max = num;\n }\n\n for (int exp = 1; max / exp > 0; exp *= 10)\n {\n CountingSortByDigit(arr, exp);\n }\n }\n\n private static void CountingSortByDigit(int[] arr, int exp)\n {\n int n = arr.Length;\n int[] output = new int[n];\n int[] count = new int[10];\n\n // Count occurrences of each digit\n foreach (int num in arr)\n {\n int digit = (num / exp) % 10;\n count[digit]++;\n }\n\n // Convert counts to positions\n for (int i = 1; i < 10; i++)\n {\n count[i] += count[i - 1];\n }\n\n // Build output array (traverse right to left for stability)\n for (int i = n - 1; i >= 0; i--)\n {\n int digit = (arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n // Copy output back to arr\n Array.Copy(output, arr, n);\n }\n\n public static void Main(string[] args)\n {\n int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};\n Sort(arr);\n Console.WriteLine(string.Join(\", \", arr));\n // Output: 2, 24, 45, 66, 75, 90, 170, 802\n }\n}\n```\n\n```rust\npub struct RadixSort;\n\nimpl RadixSort {\n pub fn radix_sort(arr: &mut Vec) {\n if arr.len() <= 1 {\n return;\n }\n\n let mut max_val = arr[0];\n for &num in arr.iter() {\n if num > max_val {\n max_val = num;\n }\n }\n\n let mut exp: i32 = 1;\n while max_val / exp > 0 {\n Self::counting_sort_by_digit(arr, exp);\n exp *= 10;\n }\n }\n\n fn counting_sort_by_digit(arr: &mut Vec, exp: i32) {\n let n = arr.len();\n let mut output = vec![0; n];\n let mut count = [0usize; 10];\n\n // Count occurrences of each digit\n for &num in arr.iter() {\n let digit = ((num / exp) % 10) as usize;\n count[digit] += 1;\n }\n\n // Convert counts to positions\n for i in 1..10 {\n count[i] += count[i - 1];\n }\n\n // Build output array (traverse right to left for stability)\n for i in (0..n).rev() {\n let digit = ((arr[i] / exp) % 10) as usize;\n output[count[digit] - 1] = arr[i];\n count[digit] -= 1;\n }\n\n // Copy output back to arr\n arr.copy_from_slice(&output);\n }\n}\n\nfn main() {\n let mut arr = vec![170, 45, 75, 90, 802, 24, 2, 66];\n RadixSort::radix_sort(&mut arr);\n println!(\"{:?}\", arr);\n // Output: [2, 24, 45, 66, 75, 90, 170, 802]\n}\n```\n\n```javascript\nfunction radixSort(arr) {\n if (arr.length <= 1) return arr;\n\n const max = Math.max(...arr);\n\n for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n\n return arr;\n}\n\nfunction countingSortByDigit(arr, exp) {\n const n = arr.length;\n const output = new Array(n);\n const count = new Array(10).fill(0);\n\n // Count occurrences of each digit\n for (const num of arr) {\n const digit = Math.floor(num / exp) % 10;\n count[digit]++;\n }\n\n // Convert counts to positions\n for (let i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n // Build output array (traverse right to left for stability)\n for (let i = n - 1; i >= 0; i--) {\n const digit = Math.floor(arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n // Copy output back to arr\n for (let i = 0; i < n; i++) {\n arr[i] = output[i];\n }\n}\n\nconst arr = [170, 45, 75, 90, 802, 24, 2, 66];\nradixSort(arr);\nconsole.log(arr);\n// Output: [2, 24, 45, 66, 75, 90, 170, 802]\n```\n\n```typescript\nfunction radixSort(arr: number[]): number[] {\n if (arr.length <= 1) return arr;\n\n const max: number = Math.max(...arr);\n\n for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {\n countingSortByDigit(arr, exp);\n }\n\n return arr;\n}\n\nfunction countingSortByDigit(arr: number[], exp: number): void {\n const n: number = arr.length;\n const output: number[] = new Array(n);\n const count: number[] = new Array(10).fill(0);\n\n // Count occurrences of each digit\n for (const num of arr) {\n const digit: number = Math.floor(num / exp) % 10;\n count[digit]++;\n }\n\n // Convert counts to positions\n for (let i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n // Build output array (traverse right to left for stability)\n for (let i = n - 1; i >= 0; i--) {\n const digit: number = Math.floor(arr[i] / exp) % 10;\n output[count[digit] - 1] = arr[i];\n count[digit]--;\n }\n\n // Copy output back to arr\n for (let i = 0; i < n; i++) {\n arr[i] = output[i];\n }\n}\n\nconst arr: number[] = [170, 45, 75, 90, 802, 24, 2, 66];\nradixSort(arr);\nconsole.log(arr);\n// Output: [2, 24, 45, 66, 75, 90, 170, 802]\n```\n\n\n---\n\n# Example Walkthrough\n\nTrace the algorithm on the array `[170, 45, 75, 90, 802, 24, 2, 66]`.\n\nThe maximum value is **802**. It has 3 digits, so the algorithm makes 3 passes.\n\n### Pass 1: Sort by Ones Digit (exp = 1)\n\nExtract the ones digit of each number using `(num / 1) % 10`:\n\n\n```shell\n170 -> digit 0\n 45 -> digit 5\n 75 -> digit 5\n 90 -> digit 0\n802 -> digit 2\n 24 -> digit 4\n 2 -> digit 2\n 66 -> digit 6\n```\n\n\nAfter counting sort by the ones digit:\n\n\n```shell\n[170, 90, 802, 2, 24, 45, 75, 66]\n 0 0 2 2 4 5 5 6\n```\n\n\n170 appears before 90 (both have ones digit 0) because 170 came first in the original array. Similarly, 802 appears before 2. Stability preserves the original ordering of ties.\n\n### Pass 2: Sort by Tens Digit (exp = 10)\n\nExtract the tens digit using `(num / 10) % 10`:\n\n\n```shell\n170 -> digit 7\n 90 -> digit 9\n802 -> digit 0\n 2 -> digit 0\n 24 -> digit 2\n 45 -> digit 4\n 75 -> digit 7\n 66 -> digit 6\n```\n\n\nAfter counting sort by the tens digit:\n\n\n```shell\n[802, 2, 24, 45, 66, 170, 75, 90]\n 0 0 2 4 6 7 7 9\n```\n\n\n802 and 2 both have tens digit 0. In the previous pass, 802 came before 2. Stability preserves this order. Similarly, 170 appears before 75 (both have tens digit 7).\n\n### Pass 3: Sort by Hundreds Digit (exp = 100)\n\nExtract the hundreds digit using `(num / 100) % 10`:\n\n\n```shell\n802 -> digit 8\n 2 -> digit 0\n 24 -> digit 0\n 45 -> digit 0\n 66 -> digit 0\n170 -> digit 1\n 75 -> digit 0\n 90 -> digit 0\n```\n\n\nAfter counting sort by the hundreds digit:\n\n\n```shell\n[2, 24, 45, 66, 75, 90, 170, 802]\n 0 0 0 0 0 0 1 8\n```\n\n\nAll the numbers with hundreds digit 0 retain their relative order from the previous pass: 2, 24, 45, 66, 75, 90. That order was correct because the previous two passes already sorted them by their tens and ones digits. The array is now fully sorted.\n\n\n```mermaid\nflowchart TD\n A[\"Original: 170, 45, 75, 90, 802, 24, 2, 66\"] --> B[\"Pass 1 (ones):
170, 90, 802, 2, 24, 45, 75, 66\"]\n B --> C[\"Pass 2 (tens):
802, 2, 24, 45, 66, 170, 75, 90\"]\n C --> D[\"Pass 3 (hundreds):
2, 24, 45, 66, 75, 90, 170, 802\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# Complexity Analysis\n\n\n| Metric | Value | Explanation |\n|--------|-------|-------------|\n| **Time** | O(d * (n + k)) | d passes, each running counting sort in O(n + k) |\n| **Space** | O(n + k) | Output array of size n, count array of size k |\n| **Stable** | Yes | Counting sort subroutine preserves relative order |\n| **In-place** | No | Requires O(n) extra space for the output array |\n| **Comparison-based** | No | Never compares two elements directly |\n\n\nWhere:\n\n- **n** = number of elements\n- **d** = number of digits in the maximum value\n- **k** = the radix (base), which is 10 for decimal numbers\n\n### When Is Radix Sort Faster Than O(n log n)?\n\nRadix sort beats comparison-based sorts when d * (n + k) < n * log(n). Since k is typically small (10 for decimal), this simplifies to roughly d < log(n).\n\nFor 1 million 32-bit integers, log2(1,000,000) is about 20, and the maximum number of decimal digits is 10. So d = 10 < 20 = log(n), and radix sort wins. For sorting 10 numbers with 100 digits each, comparison sorts are faster.\n\nRadix sort is well-suited to large datasets where the number of digits is small.\n\n### Stability\n\nLSD radix sort is stable, and stability is required for the algorithm to produce a correct result. Each pass sorts by one digit while preserving the order established by previous passes. The earlier passes sorted by less significant digits, so within each group of equal current-digit values, the elements are already in the correct relative order; stability keeps them that way.\n\nThis is why the inner sort must be a stable algorithm. Counting sort is the standard choice. Swapping in an unstable inner sort (such as quicksort or heap sort) would break the relative order from previous passes, and the final array would not be sorted.\n\n---\n\n# When to Use / When Not to Use\n\n### Good Use Cases\n\n- **Fixed-length integers:** Phone numbers, zip codes, social security numbers. The digit count is constant, which keeps d a small fixed value.\n- **Large datasets with bounded values:** Sorting millions of integers where the maximum value (and thus d) is moderate.\n- **Same-length strings:** Sorting fixed-length strings (like country codes or stock tickers) character by character.\n- **When stability is required:** Radix sort is inherently stable, which matters when sorting records by multiple keys.\n\n### Poor Use Cases\n\n- **Variable-length strings:** MSD radix sort can handle these, but the implementation is significantly more complex. For general-purpose string sorting, comparison-based sorts are often simpler and fast enough.\n- **Floating-point numbers:** The digit extraction formula does not work directly on floats. Floats must first be converted to a sortable integer representation.\n- **When d is large relative to log(n):** When numbers have many digits but the dataset is small, comparison sorts are faster.\n- **Memory-constrained environments:** Radix sort requires O(n) extra space. If memory is tight, an in-place sort like quicksort may be preferable.\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium