Radix Sort in Data Structure — Algorithm, Working and Complexity

Radix Sort is a non-comparison-based sorting algorithm that sorts integers by processing individual digits, starting from the least significant digit (LSD) to the most significant digit (MSD), using a stable sort (typically Counting Sort) at each digit position.

Working

• Find the maximum number to determine the number of digits to process.
• For each digit position (starting from the ones place), perform a stable sort of the entire array based on that digit.
• Repeat for each subsequent digit position until the most significant digit has been processed.

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for num in arr:
        count[(num // exp) % 10] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for num in reversed(arr):
        digit = (num // exp) % 10
        count[digit] -= 1
        output[count[digit]] = num
    return output

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

Complexity

Here d is the number of digits in the largest number, n is the number of elements, and k is the base used (usually 10). When d is small relative to log n, Radix Sort can outperform comparison-based sorts.

Applications

• Sorting large collections of integers with a bounded number of digits.
• Sorting fixed-width keys such as phone numbers or IDs.
• A component in suffix array and string sorting algorithms.