Radix Sort Explained: Working, Examples and Implementation

Radix Sort in data structure is a sorting method that arranges numbers by processing their digits one at a time, beginning with the least significant digit (LSD) or just the most significant digit (MSD). Unlike other sorting techniques that compare values directly, Radix Sort groups numbers based on their digit positions, making it efficient for sorting large datasets.

Why Use Radix Sort?

Because of its efficiency in sorting numbers with a fixed length, Radix Sort is used in applications like processing large numerical datasets, organizing records, and sorting phone numbers or postal codes. Here are some essential features of Radix sort:

1. Stable Sorting: It preserves the order of identical elements, ensuring that numbers with the same value remain in the same sequence as in the original list.
2. Non-Comparative Algorithm: Instead of comparing values, it sorts numbers based on their digits, which results in a temporal complexity of O(n × d), where n is the total number of elements and d is the number of digits in the biggest value.
3. Suitable for Specific Data Types: Radix Sort works well with integers, strings, and other data types that can be represented in a positional format (e.g., decimal numbers in base-10).

Stability: Why it Matters in Radix Sort

As radix sort is a stable sorting algorithm, it keeps elements with equal keys in their original order. This stability is crucial: since radix sort processes digits one at a time, each pass must preserve the order from previous passes. If an unstable method is used, the final output may be incorrect.

Key Point:
Always use a stable subroutine (like counting sort) for each digit position to ensure proper sorting.

Other Distinguishing Characteristics of Radix Sort

Besides stability, radix sort has several unique characteristics that affect its behavior and use cases:

1. Non-Comparative Sorting:
   Radix sort does not compare elements directly. Instead, it groups and processes elements based on their individual digits or characters. This allows it to avoid the lower bound of O(n log n) for comparison-based sorts.
2. Best for Certain Data Types:
   For integers, fixed-length strings, or data that can be divided into positional components (such dates or zip codes), radix sort works well. Without further treatment, it is less appropriate for floating-point values or variable-length data.
3. Auxiliary Memory Requirements:
   The algorithm needs additional space, usually O(n + k), where k is the range of possible digit values (the radix), and n is the number of items. During each digit pass, temporary arrays or buckets are stored in this area.
4. Handling Different Lengths:
   If the items to be sorted have different lengths (such as numbers with varying digits), the algorithm may pad shorter items with leading zeros to ensure all items are processed uniformly, without affecting their true value.
5. Adjustments for Negative Numbers:
   By default, radix sort works with non-negative integers. To sort negative numbers, an adjustment is needed, such as offsetting all values to be non-negative during sorting and then restoring them afterwards.

In summary:

Stability is essential for radix sort’s correctness, and its design makes it ideal for certain structured data types where comparison-based sorts are less efficient.

To truly understand how radix sort works, it helps to see the algorithm in action with concrete examples. Below, we’ll walk through the sorting process step by step using a simple data set.

For example, to sort the array [121, 432, 564, 23, 1, 45, 788], radix sort systematically arranges the numbers by each digit until the entire list is sorted.

Step 1: Find Maximum Digits

Largest element = 788 (3 digits). Thus, 3 passes are needed.

Step 2: Unit Place Sort (1st Pass)

In the first pass, radix sort looks only at the unit (ones) digit of each number.

• 121 → 1
• 432 → 2
• 564 → 4
• 23 → 3
• 1 → 1
• 45 → 5
• 788 → 8
  

Each number is placed into buckets 0–9 based on its unit digit. After placing all numbers into their respective buckets, they are collected in order from 0 to 9, preserving their original relative order.

Result after 1st pass: [121, 1, 432, 23, 564, 45, 788]

Step 3: Tens Place Sort (2nd Pass)

Next, radix sort processes the tens digit of each number from the updated list.

• 121 → 2
• 1 → 0
• 432 → 3
• 23 → 2
• 564 → 6
• 45 → 4
• 788 → 8

Again, numbers are placed into buckets according to their tens digit and collected in order.

Result after 2nd pass: [1, 121, 23, 432, 45, 564, 788]

Step 4: Hundreds Place Sort (3rd Pass)

In the final pass, radix sort examines the hundreds digit.

• 1 → 0
• 121 → 1
• 23 → 0
• 432 → 4
• 45 → 0
• 564 → 5
• 788 → 7

Numbers without a hundreds digit are treated as 0. After placing and collecting the numbers from buckets, the list becomes fully sorted.

Final Sorted Array: [1, 23, 45, 121, 432, 564, 788]

Key Takeaways from the Walkthrough

• Radix sort processes digits from the least significant to the most significant.
• At each stage, numbers are grouped and collected based on the current digit.
• The process continues until all digit places have been processed.

Readers may see how radix sort works on actual data by following this example, which offers a clear, step-by-step manual tour. Please let me know if you need any additional examples or variants (such as sorting strings or bigger data sets)!

Instead of comparing full values, Radix Sort is a non-comparative sorting algorithm that ranks objects by processing their individual digits. Starting with the Least Significant Digit (LSD) and working its way up to the Most Significant Digit (MSD), the algorithm sorts integers digit by digit.

To ensure correctness, Radix Sort uses a stable sorting algorithm, most commonly Counting Sort, at each digit position. Stability is essential because the relative order of elements from previous digit passes must be preserved.

Step-by-Step Working of the Algorithm

1. Find the maximum element in the array to determine the number of digits.
2. Start sorting from the least significant digit (units place).
3. Use Counting Sort to sort elements based on the current digit.
4. Proceed to the following digit position (hundreds, tens, etc.).
5. Continue doing this until every digit position has been processed.

Radix Sort Pseudocode

radixSort(array):
    max = findMax(array)        // Find the largest element
    exp = 1                     // Initialize digit place (1 = units)

    while max / exp > 0:
        countingSort(array, exp)
        exp = exp * 10          // Move to next digit place

countingSort(array, exp):
    size = length(array)
    output[size]
    count[10] = {0}             // Digit range 0–9

    // Count occurrences of digits
    for i = 0 to size - 1:
        index = (array[i] / exp) % 10
        count[index]++

    // Compute cumulative count
    for i = 1 to 9:
        count[i] = count[i] + count[i - 1]

    // Build output array (stable)
    for i = size - 1 downto 0:
        index = (array[i] / exp) % 10
        output[count[index] - 1] = array[i]
        count[index]--

    // Copy output to original array
    for i = 0 to size - 1:
        array[i] = output[i]

Why Counting Sort is Used

• Counting Sort is stable, which is mandatory for Radix Sort.
• It efficiently handles the limited digit range (0–9).
• It ensures the correct order is preserved across digit passes.

Bottom Line

Radix Sort works by sorting digits instead of values, and its correctness depends on using a stable sorting algorithm at every digit level.

The radix sort implementation in Java shows how this effective, non-comparative sorting algorithm sorts an array by processing numbers digit by digit.

import java.util.Arrays;

public class RadixSort {
    void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int place = 1; max / place > 0; place *= 10) {
            sortByPlace(arr, place);
        }
    }

    void sortByPlace(int[] arr, int place) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];
        
        for (int num : arr) 
            count[(num / place) % 10]++;
        
        for (int i = 1; i < 10; i++) 
            count[i] += count[i - 1];
        
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / place) % 10] - 1] = arr[i];
            count[(arr[i] / place) % 10]--;
        }
        
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        RadixSort sorter = new RadixSort();
        sorter.radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Explanation:

Radix sort is a method of sorting numbers that begins with the least significant digit and moves up to the most significant digit. It uses a reliable Counting Sort at each digit level to maintain order. The process is repeated for each place value (ones, tens, hundreds, etc.) until the largest number is fully sorted. Radix Sort is effective for huge datasets since it usually runs in O(nd) time when assessing time complexity.

Output:

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

Time and Space Complexity:

• Radix Sort Time Complexity: Best, Average, and Worst Case: O(nd), where n is the number of elements, and d is the number of digits in the largest number.
• Space Complexity: O(n), due to the extra output array used in each pass.

As it uses another sorting technique as a crucial part of its operation, radix sort stands apart among sorting algorithms. In particular, for radix sort to accurately sort objects by each digit or character position, a stable sorting algorithm is needed. The most common auxiliary algorithm used is counting sort, but other stable sorts, such as bubble sort, can also be used, depending on the requirements and constraints of your data or implementation.

Why Use an Auxiliary Sorting Algorithm?

At each digit position, radix sort groups elements based on their current digit. To maintain the correct ordering established in previous passes (which is essential for radix sort’s correctness), the sorting algorithm used for each digit must be stable. A stable sort keeps elements with the same digit in the same relative order as before, ensuring the final result is accurate.

Common Choices: Counting Sort and Beyond

• Counting Sort: As it is consistent and effective for sorting numbers inside a specific range (such as the digits 0–9 in decimal numbers), this is the most widely used radix sort option. Radix sort is quite effective in practice since counting sort has linear time complexity for narrow ranges.
• Bubble Sort or Other Stable Sorts: While less common due to lower efficiency, any stable sorting algorithm can be used for the digit-wise sorting step. For example, bubble sort may be chosen in educational settings or for very small datasets.

Example Scenario:

If you need to sort a list of phone numbers, radix sort will process each digit from right to left. For each digit, it will use a stable sort (like counting sort) to order the numbers according to the current digit, preserving the order of numbers with the same digit in previous passes.

Flexibility and Comparisons with Other Algorithms

Unlike comparison-based algorithms such as quicksort or mergesort, radix sort does not compare entire values. However, in real-world applications, radix sort may be combined with these algorithms:

• Radix sort is used to efficiently group data in huge datasets with lengthy keys. A comparison-based sort is then used for final ordering or for data types that don't meet radix sort's requirements.
• In hybrid approaches, different sorting algorithms may be used for different data segments, depending on the data’s characteristics.

Key Takeaways

• Radix sort relies on a stable auxiliary sorting algorithm for each digit; counting sort is the most common choice.
• Other stable algorithms, like bubble sort, can be used, though they may be less efficient.
• Radix sort’s reliance on auxiliary sorts gives it flexibility, but the choice of subroutine impacts overall performance.
• In some cases, radix sort is combined with comparison-based algorithms for optimal results with mixed or complex datasets.

• Fast for Large Datasets (Under Certain Conditions): Radix Sort has a time complexity of O(nd), which can be quicker than comparison-based sorting algorithms such as QuickSort (O(n log n)) when the number of digits (d) is small in contrast to the number of items. This makes it highly efficient for sorting large datasets with limited-digit numbers.
• Stable Sorting Algorithm: Unlike other sorting algorithms, Radix Sort keeps the relative order of elements with the same key. This is very handy when sorting data according to various properties.
• Ideal for Certain Data Types: Radix Sort is ideal for sorting integers, fixed-length strings, and data with tiny digit ranges (such as dates or zip codes). Because it does not rely on comparisons, it may be more reliable and speedier in certain instances.

• Higher Memory Usage: The algorithm requires extra space proportional to the size of the input (O(n + k), at which k is the range of digits or characters used). This additional memory can be a concern for very large datasets.
• Limited Flexibility with Data Types: Radix Sort works well for sorting fixed-length strings and integers, but it is not appropriate for sorting variable-length data or floating-point values. Additional processing is required when handling several data kinds.
• Performance Drops with Large Digits: The speed may deteriorate considerably if the numbers being sorted contain a large number of digits. Since Radix Sort processes each digit separately, large-digit numbers require more iterations, slowing down the sorting process.

Radix sort is known for its efficiency in sorting large collections of data, particularly when the data consists of integers or strings with a fixed length. To evaluate its performance, we analyze both time and space complexity.

Time Complexity

Three primary elements determine the radix sort's time complexity:

1. n: The quantity of items to be sorted.
2. k: The length of the longest string or the number of digits in the greatest element.
3. b: The numerical system's basis, such as 2 for binary and 10 for decimal.

Each element's digit is processed using radix sort, usually starting with the least important digit and working up to the most important one. A reliable sorting algorithm—typically counting sort—is used for every digit location. One way to represent the whole temporal complexity is:

O(n × k)

Radix sort is very effective for sorting big datasets with fixed-length keys because it achieves linear time complexity, O(n), if all integers are of comparable length (k is constant). However, the complexity may go close to O(n log n) if the number of digits k rises with n (for instance, sorting very huge integers).

Space Complexity

Radix sort is not an in-place algorithm. It requires additional memory for temporary storage during the sorting of each digit. The space complexity is:

O(n + b)

Here, O(n) is for the output array, and O(b) is for counting occurrences of each digit (where b is the base). This means radix sort can be memory-intensive, especially with large bases or large datasets.

Comparison with Other Sorting Algorithms

Radix Sort performs better than comparison-based sorting methods when d is much less than log⁡n. In terms of Radix Sort time complexity, it can achieve linear time performance under ideal conditions. However, because it requires more space, it is less memory-efficient than in-place algorithms like QuickSort.

1. Sorting Numeric IDs and Phone Numbers

When arranging lengthy numerical data, including employee IDs, phone numbers, and account numbers, where each digit may be handled separately without comparisons, Radix Sort works effectively. Sorting becomes predictable and quick as a result.

2. Lexicographical Sorting of Strings

Radix sort is excellent for arranging words in dictionaries or search indexes because, although it was first created for numbers, it can also be used to sort strings alphabetically, particularly when the strings are of equal or restricted length.

3. Used in Fixed-Length Record Sorting

Radix sort is helpful when comparison-based algorithms like quicksort or mergesort are not optimal, particularly in hardware-level applications or digital systems, because it doesn't rely on comparison operators.

4. Used in Non-Comparative Sorting Requirements

Radix Sort does not require comparing two items for a person to sort through. Thus, Radix Sort is useful for applications where using a comparison-based sorting method would result in inefficiencies (ex. hardware systems and digital systems).

5. High-Performance Systems (e.g., GPUs and Parallel Computing)

Parallel computing is made possible by the Radix Sort method's digit-wise structure. High-performance computing systems, including those that handle big datasets or make use of graphics processing units (GPUs), may often benefit from parallel computing. In high-performance computing, the main benefit of Radix Sort is that comparison-based sorting techniques can lead to bottlenecks.

6. Compiler Design and Text Processing

The Radix Sort function in compiler design makes it possible to quickly seek for identifiers and keywords in the final produced source code while simultaneously sorting them effectively. For text processing tasks where positional character elements (prefixes and suffixes) are utilized, Radix Sort is very helpful.

When other sorting techniques fail, the radix sort algorithm performs well for rapidly sorting fixed-size keys. Nevertheless, it has several disadvantages, such as requiring additional space and being restricted to specific data kinds. In spite of this, it is really helpful for arranging a lot of words. Understanding radix sort helps developers improve their sorting skills when they need a stable and efficient method.

Points to Remember

1. Radix Sort processes elements one digit or character position at a time, not by comparing full values.
2. The correctness of Radix Sort depends on using a stable sorting algorithm (such as Counting Sort) at each digit level.
3. Radix Sort can work in linear time O(n × d) when the number of digits is small and fixed.
4. It is best suited for integers and fixed-length strings, not for floating-point or highly variable-length data.
5. Extra memory is required during sorting, which means Radix Sort is not an in-place algorithm.

1. What is the time complexity of Radix Sort?

The temporal complexity of Radix Sort is O(nd), where d is the number of digits in the greatest number and n is the number of items. When dealing with fixed-size integers (like 32-bit numbers), it performs very efficiently, often faster than comparison-based algorithms like QuickSort, which runs in O(n log n).

2. Is Radix Sort a stable sorting algorithm?

Yes, Radix Sort maintains the relative order of items with the same value. The order created in previous phases is maintained in subsequent runs since it sorts digit by digit.

3. When is Radix Sort better than QuickSort?

Radix Sort is useful when sorting large datasets of integers or fixed-length strings. If the number of digits (d) is relatively small, Radix Sort can be faster than QuickSort because it avoids the O(n log n) comparisons. For instance, sorting millions of 10-digit numbers with Radix Sort is more efficient than using QuickSort.

4. What is the difference between LSD and MSD Radix Sort?

Radix Sort comes in two varieties:

• Numbers are sorted using LSD (Least Significant Digit), which begins with the rightmost digit and moves leftward. It is frequently applied to fixed-length data and integers since it is steady.
• The leftmost digit is when MSD (Most Significant Digit) starts sorting. It is less stable and more complicated than LSD, but it functions well for strings of varying lengths.

5. Can Radix Sort handle negative numbers?

Yes, however, a minor modification is needed. Shifting all integers by adding the absolute value of the smallest negative number is one popular method. Before sorting, this makes everything non-negative. The numbers are sorted and then returned to their initial values.

6. What are the limitations of Radix Sort?

Radix Sort has a few disadvantages.

• Additional Memory: The amount of extra memory required is about O(n + k), where k is the radix size (such as 10 for decimal values).
• Not Perfect for Every Data Set: Additional processes are needed when sorting variable-length data or floating-point values.
• Slower for Large Digits: Performance may deteriorate if d (the number of digits) is large, making it less effective for really large integers (such as 64-bit values).