Mastering Algorithms

Radix Sort

Overview

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing individual digits. It works by sorting the numbers digit by digit, starting from the least significant digit (LSD) or most significant digit (MSD).

Unlike comparison-based sorting algorithms, Radix Sort doesn't compare elements directly. Instead, it uses the digits of the numbers to distribute them into buckets, making it potentially faster than comparison-based algorithms for certain types of data.

How It Works

The algorithm works by:

  1. Finding the maximum number to determine the number of digits
  2. For each digit position (from least to most significant):
  3. Distribute numbers into buckets based on the current digit (0-9)
  4. Collect numbers from buckets in order
  5. Repeat for the next digit position

The algorithm uses a stable sorting algorithm (typically counting sort) as a subroutine for each digit position.

Algorithm


RadixSort(arr):
    max_val = find maximum value in arr
    exp = 1  // Start with least significant digit
    
    while max_val / exp > 0:
        counting_sort(arr, exp)
        exp *= 10  // Move to next digit

CountingSort(arr, exp):
    n = length of arr
    output = array of size n
    count = array of size 10, initialized to 0
    
    // Count occurrences of each digit
    for i = 0 to n - 1:
        index = (arr[i] / exp) % 10
        count[index]++
    
    // Change count to position
    for i = 1 to 9:
        count[i] += count[i - 1]
    
    // Build output array
    for i = n - 1 down to 0:
        index = (arr[i] / exp) % 10
        output[count[index] - 1] = arr[i]
        count[index]--
    
    // Copy output to arr
    for i = 0 to n - 1:
        arr[i] = output[i]

Implementation


def counting_sort(arr, exp):
    """Counting sort as subroutine for radix sort"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # Count occurrences of each digit
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    
    # Change count to position
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Build output array
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    
    # Copy output to arr
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    """Radix sort implementation"""
    if not arr:
        return arr
    
    # Find maximum number to know number of digits
    max_val = max(arr)
    
    # Do counting sort for every digit
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    
    return arr

Complexity Analysis

  • Time Complexity:
    • Best/Average/Worst Case: O(d × (n + k)) where d is number of digits, n is array size, k is range (10 for decimal)
    • For integers: O(n × d) where d is the number of digits in the maximum number
  • Space Complexity: O(n + k) - for output array and count array

Radix Sort's performance depends on the number of digits. For numbers with a fixed number of digits (like 32-bit integers), it can be O(n), making it very efficient for large datasets of integers.

Characteristics

  • Stable: Yes - when using stable counting sort
  • In-place: No - requires O(n) extra space
  • Adaptive: No - always performs the same operations
  • Online: No - requires the entire array
  • Non-comparison: Yes - doesn't compare elements directly

When to Use Radix Sort

Radix Sort is ideal when:

  • Sorting integers or strings with fixed-length keys
  • Keys have a limited range of values
  • You need stable sorting
  • Sorting large datasets of integers
  • When the number of digits is small compared to the array size

Not suitable for:

  • Floating-point numbers (without modification)
  • Variable-length keys
  • When memory is severely limited

Example

Sorting [170, 45, 75, 90, 2, 802, 24, 66]: 

Initial: [170, 45, 75, 90, 2, 802, 24, 66]

Pass 1 (ones place):
  [170, 90, 2, 802, 24, 45, 75, 66]

Pass 2 (tens place):
  [2, 802, 24, 45, 66, 170, 75, 90]

Pass 3 (hundreds place):
  [2, 24, 45, 66, 75, 90, 170, 802]

Sorted: [2, 24, 45, 66, 75, 90, 170, 802]

Related Algorithms

Explore other sorting algorithms: