Skip to main content

​
Overview

Radix Sort is a non-comparison-based sorting algorithm that sorts integers by processing individual digits. It processes digits from the least significant digit (LSD) to the most significant digit (MSD), using a stable sorting algorithm (typically Counting Sort) as a subroutine. Radix Sort can achieve linear time complexity when the number of digits is constant.

​
Implementation

function countingSort(
  list: number[],
  radixBase: number,
  significantDigit: number
) {
  const aux: number[] = [];
  const counts: number[] = new Array(radixBase).fill(0);

  // Store count of occurrences in counts[]
  for (let i = 0; i < list.length; i++) {
    counts[Math.floor(list[i] / significantDigit) % radixBase]++;
  }

  // Change counts[i] so that counts[i] now contains the actual position
  // of this digit in aux[]
  for (let i = 1; i < radixBase; i++) {
    counts[i] += counts[i - 1];
  }

  // Build the aux array
  for (let i = list.length - 1; i >= 0; i--) {
    const bucketIndex = Math.floor(list[i] / significantDigit) % radixBase;

    aux[--counts[bucketIndex]] = list[i];
  }

  // Copy the aux array to list[], so that list[] now
  // contains sorted numbers according to current digit
  for (let i = 0; i < list.length; i++) {
    list[i] = aux[i];
  }
}

export function radixSort(list: number[], radixBase = 10) {
  if (list.length < 2) {
    return list;
  }

  const max = Math.max(...list);

  for (let digit = 1; Math.floor(max / digit) > 0; digit *= radixBase) {
    countingSort(list, radixBase, digit);
  }

  return list;
}

​
How It Works

  1. Find Maximum: Determine the number with the most digits to know how many passes are needed
  2. Process Each Digit: Starting from the least significant digit (rightmost)
  3. Stable Sort: Use a stable sort (Counting Sort) to sort by the current digit
  4. Move to Next Digit: Multiply the digit position by the radix base and repeat
  5. Complete: After processing all digits, the array is fully sorted
Radix Sort requires a stable subroutine sorting algorithm. If the subroutine isn’t stable, equal elements might be reordered, breaking the algorithm’s correctness.

​
Complexity Analysis

Time Complexity

  • Best Case: O(d(n + k))
  • Average Case: O(d(n + k))
  • Worst Case: O(d(n + k))
  • Where d = number of digits, k = radix base

Space Complexity

  • Space: O(n + k) for auxiliary arrays
  • Auxiliary: O(n) for output array
  • Counting Array: O(k) where k is radix base

​
Usage Example

import { radixSort } from './radix-sort';

// Example 1: Sort decimal numbers (default base 10)
const numbers = [170, 45, 75, 90, 802, 24, 2, 66];
const sorted = radixSort(numbers);
console.log(sorted); // [2, 24, 45, 66, 75, 90, 170, 802]

// Example 2: Sort with custom radix base (binary, base 2)
const binary = [5, 2, 8, 1, 9, 3, 7];
const sortedBinary = radixSort(binary, 2);
console.log(sortedBinary); // [1, 2, 3, 5, 7, 8, 9]

// Example 3: Large numbers
const large = [329, 457, 657, 839, 436, 720, 355];
radixSort(large); // [329, 355, 436, 457, 657, 720, 839]

// Example 4: Numbers with same digits
const sameDigits = [111, 222, 333, 444, 555];
radixSort(sameDigits); // [111, 222, 333, 444, 555]

​
Visual Example

Let’s trace through sorting [170, 45, 75, 90, 2, 802, 24, 66] with radix base 10: 
Initial: [170, 45, 75, 90, 2, 802, 24, 66]

### Pass 1: Sort by ones place (digit = 1)
Extract ones digit: [0, 5, 5, 0, 2, 2, 4, 6]
Sort by ones place: [170, 90, 2, 802, 24, 45, 75, 66]
                     (0) (0)(2) (2) (4) (5) (5) (6)

### Pass 2: Sort by tens place (digit = 10)
Extract tens digit:  [7, 9, 0, 0, 2, 4, 7, 6]
Sort by tens place:  [2, 802, 24, 45, 66, 170, 75, 90]
                     (0) (0) (2) (4) (6) (7)  (7) (9)

### Pass 3: Sort by hundreds place (digit = 100)
Extract hundreds:    [0, 8, 0, 0, 0, 1, 0, 0]
Sort by hundreds:    [2, 24, 45, 66, 75, 90, 170, 802]
                     (0)(0) (0)(0)(0)(0) (1)  (8)

Final: [2, 24, 45, 66, 75, 90, 170, 802]
Detailed Pass 1 (sorting by ones digit): 
Ones digits: 0, 5, 5, 0, 2, 2, 4, 6

Counting Sort:
  Count occurrences:
    counts = [2, 0, 2, 0, 1, 2, 1, 0, 0, 0]
    indices:  0  1  2  3  4  5  6  7  8  9
  
  Cumulative counts:
    counts = [2, 2, 4, 4, 5, 7, 8, 8, 8, 8]
  
  Place elements:
    170 (ones=0) → position 1
    90  (ones=0) → position 0
    2   (ones=2) → position 3
    802 (ones=2) → position 2
    24  (ones=4) → position 4
    45  (ones=5) → position 6
    75  (ones=5) → position 5
    66  (ones=6) → position 7
  
  Result: [90, 170, 802, 2, 24, 75, 45, 66]

​
Characteristics

Radix Sort is stable when using a stable subroutine (like the Counting Sort implementation shown). Equal elements maintain their relative order.
No, Radix Sort is not in-place. It requires O(n + k) additional space for the auxiliary and counting arrays.
No, Radix Sort is not adaptive. It processes all digits regardless of the initial order.
No, Radix Sort is not comparison-based. It processes digits directly, allowing it to achieve linear time complexity.

​
When to Use

Radix Sort excels when sorting integers with a fixed number of digits or when digit count is small relative to n.
Good for:
  • Sorting integers with a known maximum value
  • When the number of digits d is small (d << log n)
  • Sorting fixed-length strings or keys
  • When linear time sorting is needed
  • Parallel processing (each digit can be processed independently)
  • Large datasets with small key sizes
Avoid when:
  • Sorting floating-point numbers (requires conversion)
  • Variable-length strings (requires padding)
  • Very large digit counts (d approaches n)
  • Memory is extremely limited
  • Small datasets (overhead not worth it)

​
Performance Insights

When Radix Sort Beats Comparison Sorts:For n integers with d digits in base k:
  • Radix Sort: O(d(n + k))
  • Quick Sort: O(n log n)
Example: Sorting 1 million 32-bit integers
  • d = 4 (for 8-digit hex numbers, processing 2 digits at a time)
  • k = 256 (using byte-sized buckets)
  • Radix Sort: 4 × (1,000,000 + 256) ≈ 4 million operations
  • Quick Sort: 1,000,000 × log(1,000,000) ≈ 20 million operations
  • Result: Radix Sort is ~5x faster!

​
Radix Base Selection

Choosing radix base k affects performance:

Larger k (e.g., k=256):
  + Fewer passes (smaller d)
  + Less iteration overhead
  - Larger counting array
  - More memory usage
  
Smaller k (e.g., k=10):
  + Less memory for counting
  + More intuitive for decimal numbers
  - More passes needed
  - More iteration overhead

Optimal: k = Θ(n) often gives best performance
Common choices: 10 (decimal), 256 (byte), 2^16 (word)

​
Code Walkthrough

​
Helper Function: countingSort()

function countingSort(
  list: number[],
  radixBase: number,      // Base of number system (10 for decimal)
  significantDigit: number // Power of radix (1, 10, 100, ...)
) {
  const aux: number[] = [];
  const counts: number[] = new Array(radixBase).fill(0);

  // Count occurrences of each digit
  for (let i = 0; i < list.length; i++) {
    const digit = Math.floor(list[i] / significantDigit) % radixBase;
    counts[digit]++;
  }

  // Convert to cumulative counts (positions)
  for (let i = 1; i < radixBase; i++) {
    counts[i] += counts[i - 1];
  }

  // Build sorted array (right to left for stability)
  for (let i = list.length - 1; i >= 0; i--) {
    const digit = Math.floor(list[i] / significantDigit) % radixBase;
    aux[--counts[digit]] = list[i];
  }

  // Copy back to original array
  for (let i = 0; i < list.length; i++) {
    list[i] = aux[i];
  }
}

​
Main Function: radixSort()

export function radixSort(list: number[], radixBase = 10) {
  if (list.length < 2) {
    return list;
  }

  // Find maximum to determine number of digits
  const max = Math.max(...list);

  // Process each digit from least to most significant
  for (let digit = 1; Math.floor(max / digit) > 0; digit *= radixBase) {
    countingSort(list, radixBase, digit);
  }

  return list;
}

​
LSD vs MSD Radix Sort

Two Variants:LSD (Least Significant Digit) - Shown here:
  • Processes digits from right to left
  • Simpler to implement
  • Always stable
  • Sorts entire array at once
  • Better for fixed-length keys
MSD (Most Significant Digit):
  • Processes digits from left to right
  • More complex (requires recursion)
  • Can be faster by early termination
  • Better for variable-length keys
  • Used in string sorting

​
Comparison with Other Sorts

AlgorithmBest CaseAverage CaseWorst CaseSpaceStableData Type
Radix SortO(d(n + k))O(d(n + k))O(d(n + k))O(n + k)YesIntegers
Counting SortO(n + k)O(n + k)O(n + k)O(k)Yes*Integers
Quick SortO(n log n)O(n log n)O(n²)O(log n)NoAny
Merge SortO(n log n)O(n log n)O(n log n)O(n)YesAny
Heap SortO(n log n)O(n log n)O(n log n)O(1)NoAny

​
Real-World Applications

Where Radix Sort is Used:
  1. Suffix Array Construction: Text indexing algorithms
  2. IP Address Sorting: Network routing tables
  3. Date Sorting: Year-month-day format
  4. Card Sorting: Suit and rank
  5. Lexicographic Ordering: Dictionary sorting
  6. Database Indexing: Integer key sorting
  7. Parallel Processing: GPU sorting algorithms

​
Optimizations

Common Optimizations:
  1. Byte-wise Radix: Use k=256 and process one byte at a time
  2. Hybrid Approach: Switch to Insertion Sort for small subarrays
  3. Skip Leading Zeros: For sparse numbers, skip empty digit positions
  4. Two-pass Optimization: Process two digits per pass
  5. Parallel Counting: Distribute counting across multiple threads

​
Handling Negative Numbers

To sort arrays with negative numbers: 
function radixSortWithNegatives(list: number[]) {
  // Separate positive and negative numbers
  const negatives = list.filter(n => n < 0).map(n => -n);
  const positives = list.filter(n => n >= 0);
  
  // Sort both using radix sort
  radixSort(negatives);
  radixSort(positives);
  
  // Combine: reversed negatives (now positive) then positives
  return [...negatives.reverse().map(n => -n), ...positives];
}

​
Why It’s Called “Radix”

The term “radix” is Latin for “root” and in mathematics refers to the base of a number system. Radix Sort is named after this because it processes numbers digit-by-digit in a particular radix (base), such as:
  • Radix 10 (decimal): digits 0-9
  • Radix 2 (binary): digits 0-1
  • Radix 16 (hexadecimal): digits 0-F
  • Radix 256 (byte): values 0-255

Build docs developers (and LLMs) love

Get started for freeTalk to us