{"title":"Radix Sort","description":"","content":"Radix Sort is a non-comparison-based sorting algorithm that processes elements digit by digit, starting from the least significant digit to the most significant (or vice versa). Instead of comparing values directly, it groups elements based on their digits at each position.\n\nAt each step, a stable sorting algorithm like Counting Sort is used to reorder the elements according to the current digit. By repeating this process across all digits, the array becomes fully sorted.\n\nRadix Sort achieves linear time complexity O(n · d), where d is the number of digits, making it efficient for sorting large sets of integers or strings with fixed length.\n\nIn this chapter, you will learn how Radix Sort works step by step, how it builds on Counting Sort, and when it is a better choice than 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 we will focus on. 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\nThe key insight is that each 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. This is critical. Without stability, sorting by the tens digit would destroy the ordering we established when sorting by the ones digit. Counting sort is the standard choice for this subroutine because it is stable, runs in O(n + k) time, and works perfectly 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):\n\n- Use counting sort to sort the array based on the current digit.\n- The counting sort only looks at one digit of each number, not the entire number.\n\n1. 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\nTo isolate the digit at a given position, we use 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\nThis is the part that trips people up. How can sorting by the least significant digit first produce a correct result?\n\nThe answer is **stability**. When we sort by the ones digit, all numbers with the same ones digit are grouped together. When we then sort by the tens digit, numbers with the same tens digit are grouped, but within each group, the relative order from the ones-digit pass is preserved. By the time we reach the most significant digit, each pass has refined the ordering, and stability ensures that earlier passes are never undone.\n\nThink of it like sorting a spreadsheet. If you sort 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. That is exactly what LSD radix sort does with digit positions.\n\n---\n\n# Code Implementation\n\n### Counting Sort as Subroutine\n\nBefore implementing radix sort, we need 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 we are sorting by (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\nLet us trace through the algorithm with the array `[170, 45, 75, 90, 802, 24, 2, 66]`.\n\nFirst, we find the maximum value: **802**. It has 3 digits, so we need 3 passes.\n\n### Pass 1: Sort by Ones Digit (exp = 1)\n\nWe extract 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\nNotice that 170 appears before 90 (both have ones digit 0) because 170 came first in the original array. Similarly, 802 appears before 2. Stability at work.\n\n### Pass 2: Sort by Tens Digit (exp = 10)\n\nWe extract 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\nWe extract 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\nFor radix sort to beat comparison-based sorts, we need 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 would be faster.\n\nThe takeaway: radix sort shines when the number of digits is small and the dataset is large.\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, making 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 you need stability:** 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. You would need to convert to a sortable integer representation first.\n- **When d is large relative to log(n):** If your numbers have many digits but your dataset is small, comparison sorts will be 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.","pageType":"dsa"}

Radix Sort

Ashish Pratap Singh

Get Premium