Radix Sort Algorithm: Digit-by-Digit Sorting Technique Explained with Examples

Sorting algorithms are fundamental to computer science, and one unique member of the family is the Radix Sort algorithm. Unlike comparison-based algorithms such as Quick Sort or Merge Sort, Radix Sort uses the individual digits of numbers to organize data. This makes it especially efficient in certain scenarios, particularly when working with integers and fixed-length data. In this article, we will explore how Radix Sort works, its advantages, detailed step-by-step examples, and Python implementation along with complexity analysis.

Table of Contents

What is Radix Sort?

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers digit by digit. It processes digits either from the Least Significant Digit (LSD) to the Most Significant Digit (MSD), or vice-versa. At each step, a stable sorting algorithm (commonly Counting Sort) is applied to group elements based on the current digit under examination.

Key Characteristics of Radix Sort

Stable Sorting: Uses stable sub-sorting like Counting Sort to preserve order of equal elements.
Digit-by-Digit Sorting: Works on digits indexed from rightmost (LSD) or leftmost (MSD).
Non-Comparative: Unlike Quick Sort or Merge Sort, it does not compare numbers directly.
Linear Time Potential: Achieves O(nk) complexity, where n is the number of elements and k is the number of digits.

How Does Radix Sort Work?

The algorithm follows these steps:

Find the maximum number in the dataset to determine the number of digits.
Sort elements digit by digit.
Use a stable sorting method like Counting Sort for each digit.
Combine results, progressively leading to a fully sorted array.

Example of Radix Sort

Let’s sort the array: [170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Sort by Least Significant Digit (1s place)

Original: [170, 45, 75, 90, 802, 24, 2, 66]
After 1s digit sorting: [170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by 10s place

After 10s digit sorting: [802, 2, 24, 45, 66, 170, 75, 90]

Step 3: Sort by 100s place

After 100s digit sorting: [2, 24, 45, 66, 75, 90, 170, 802]
Final Result: [2, 24, 45, 66, 75, 90, 170, 802]

Interactive Visualization of Radix Sort

You can simulate Radix Sort by writing a small interactive program that shows each digit-based pass. Try running the Python example below. Each pass will display the intermediate results for clarity.

Python Implementation of Radix Sort


def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # Count occurrences
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # Cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build output array
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    # Copy to original
    for i in range(n):
        arr[i] = output[i]


def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        print(f"Sorting by exp {exp}: {arr}")  # Visual step
        exp *= 10


arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original:", arr)
radix_sort(arr)
print("Sorted:", arr)

Time Complexity of Radix Sort

Best Case: O(nk)
Average Case: O(nk)
Worst Case: O(nk)

Where n = number of elements, and k = number of digits in the maximum number. Since k is usually much smaller than n, Radix Sort performs close to linear time for practical input ranges.

When to Use Radix Sort?

Radix Sort is best suited when:

Data is numerical and uniform in length (like integers with bounded digit size).
You need linear time complexity performance for large datasets.
Stability of sorting is important.

Advantages of Radix Sort

Efficient for sorting large datasets of integers or strings with fixed length.
Stable sorting keeps equal keys in their original order.
Runs in near-linear time when digit size is small compared to input size.

Limitations of Radix Sort

Not always practical due to high memory usage in Counting Sort subroutine.
Performance depends on digit size (k). If k is significant, it may become inefficient.
Typically less flexible compared to comparison-based algorithms.

Conclusion

The Radix Sort algorithm is a powerful technique for scenarios where data can be broken down digit by digit. While it’s not universally optimal, it excels in cases like sorting large sets of integers or strings with predictable length. Its ability to operate without comparisons sets it apart and makes it a crucial algorithm to learn in computer science.