Radix Sort

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

Find Maximum: Determine the number with the most digits to know how many passes are needed
Process Each Digit: Starting from the least significant digit (rightmost)
Stable Sort: Use a stable sort (Counting Sort) to sort by the current digit
Move to Next Digit: Multiply the digit position by the radix base and repeat
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

Stability

Radix Sort is stable when using a stable subroutine (like the Counting Sort implementation shown). Equal elements maintain their relative order.

In-Place

No, Radix Sort is not in-place. It requires O(n + k) additional space for the auxiliary and counting arrays.

Adaptive

No, Radix Sort is not adaptive. It processes all digits regardless of the initial order.

Comparison-Based

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

Algorithm	Best Case	Average Case	Worst Case	Space	Stable	Data Type
Radix Sort	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	Yes	Integers
Counting Sort	O(n + k)	O(n + k)	O(n + k)	O(k)	Yes*	Integers
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Any
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Any
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Any

Real-World Applications

Where Radix Sort is Used:

Suffix Array Construction: Text indexing algorithms
IP Address Sorting: Network routing tables
Date Sorting: Year-month-day format
Card Sorting: Suit and rank
Lexicographic Ordering: Dictionary sorting
Database Indexing: Integer key sorting
Parallel Processing: GPU sorting algorithms

Optimizations

Common Optimizations:

Byte-wise Radix: Use k=256 and process one byte at a time
Hybrid Approach: Switch to Insertion Sort for small subarrays
Skip Leading Zeros: For sparse numbers, skip empty digit positions
Two-pass Optimization: Process two digits per pass
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

Get Started

Data Structures

Algorithms

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Design Techniques

Overview

Implementation

How It Works

Complexity Analysis

Time Complexity

Space Complexity

Usage Example

Visual Example

Characteristics

When to Use

Performance Insights

Radix Base Selection

Code Walkthrough

Helper Function: `countingSort()`

Main Function: `radixSort()`

LSD vs MSD Radix Sort

Comparison with Other Sorts

Real-World Applications

Optimizations

Handling Negative Numbers

Why It’s Called “Radix”

Build docs developers (and LLMs) love

Get Started

Data Structures

Algorithms

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Design Techniques

​Overview

​Implementation

​How It Works

​Complexity Analysis

Time Complexity

Space Complexity

​Usage Example

​Visual Example

​Characteristics

​When to Use

​Performance Insights

​Radix Base Selection

​Code Walkthrough

​Helper Function: countingSort()

​Main Function: radixSort()

​LSD vs MSD Radix Sort

​Comparison with Other Sorts

​Real-World Applications

​Optimizations

​Handling Negative Numbers

​Why It’s Called “Radix”

Build docs developers (and LLMs) love

Overview

Implementation

How It Works

Complexity Analysis

Usage Example

Visual Example

Characteristics

When to Use

Performance Insights

Radix Base Selection

Code Walkthrough

Helper Function: `countingSort()`

Main Function: `radixSort()`

LSD vs MSD Radix Sort

Comparison with Other Sorts

Real-World Applications

Optimizations

Handling Negative Numbers

Why It’s Called “Radix”