Radix Sort Algorithm | Working, Applications & More (+Example)

0 min read

Sorting algorithms play a crucial role in computer science, enabling efficient organization and retrieval of data. Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits, from the least significant to the most significant. Unlike comparison-based sorting techniques like QuickSort or MergeSort, Radix Sort leverages digit placement to achieve an efficient time complexity of O(nk), where n is the number of elements and k is the number of digits in the largest number.

In this article, we will explore the working of Radix Sort, its implementation, advantages, and scenarios where it outperforms traditional sorting algorithms. 

Understanding Radix Sort Algorithm

Sorting is a fundamental operation in computer science, helping us arrange data in a specific order for efficient searching and processing. Radix Sort is a unique sorting algorithm that does not rely on comparisons like QuickSort or MergeSort algorithm. Instead, it sorts numbers digit by digit, making it highly efficient for large datasets with uniform-length numbers.

Apply Now

Working Of Radix Sort Algorithm

Radix Sort in data structures works by processing individual digits of numbers, starting from either the Least Significant Digit (LSD) (rightmost digit) or the Most Significant Digit (MSD) (leftmost digit). It repeatedly groups numbers based on their current digit and sorts them into "buckets" before moving to the next digit. This process continues until all digits are processed, resulting in a fully sorted list.

Real-Life Analogy: Sorting Papers In Mailboxes

Imagine you work in a mailroom, sorting thousands of letters by postal codes. Instead of comparing entire postal codes at once, you sort them digit by digit:

1. First Round (Rightmost Digit) – You place all letters into ten separate bins based on the last digit of their postal code (0–9).
2. Second Round (Next Digit) – You pick up the letters from the bins and sort them again based on the second-last digit.
3. Continue Until All Digits Are Sorted – By the time you reach the first digit, the letters are perfectly arranged in order.

Just like sorting mail, Radix Sort ensures numbers are correctly ordered by processing each digit step by step!

How Does The Radix Sort Algorithm Work?

Radix Sort is a digit-based, non-comparative sorting algorithm that processes numbers by their individual digits rather than comparing entire values. It sorts numbers by grouping them based on each digit, from either the Least Significant Digit (LSD) (rightmost) or the Most Significant Digit (MSD) (leftmost).

Concept Of Digit-Based Sorting

Unlike comparison-based algorithms like QuickSort and MergeSort, Radix Sort works by:

1. Distributing numbers into buckets based on the value of the current digit being processed.
2. Collecting the numbers from the buckets in order.
3. Repeating the process for the next digit until all digits have been sorted.

Since this method relies on individual digits, it is especially efficient for sorting large numbers with uniform lengths, such as phone numbers, zip codes, or large datasets.

Explanation Of LSD And MSD Approaches

Radix Sort can be implemented in two ways:

1. Least Significant Digit (LSD) Approach

• Starts sorting from the rightmost digit (units place) and moves left.
• After processing all digits, numbers are sorted correctly.
• Typically implemented using counting sort as a stable subroutine.
• Commonly used in practical implementations due to its simplicity.

Example: Sorting {329, 457, 657, 839, 436, 720, 355} using LSD

• Sort by units place:

720, 329, 839, 355, 457, 657, 436  

• Sort by tens place:

720, 329, 436, 839, 355, 457, 657  

• Sort by hundreds place:

329, 355, 436, 457, 657, 720, 839  

• Final sorted order:

{329, 355, 436, 457, 657, 720, 839}

2. Most Significant Digit (MSD) Approach

• Starts sorting from the leftmost digit (highest place value) and moves right.
• Uses recursive bucket sorting (like a tree structure).
• Less common but useful for sorting variable-length numbers like strings or IP addresses.

Code Implementation Of Radix Sort Algorithm

Here’s the C++ implementation of Radix Sort, using Counting Sort as a stable sorting technique for each digit place.

Code Example:

            #include 
#include 
#include 

using namespace std;

// Function to get the maximum value in the array
int getMax(const vector& arr) {
    return *max_element(arr.begin(), arr.end());
}

// Function to perform Counting Sort based on a specific digit place
void countingSort(vector& arr, int exp) {
    int n = arr.size();
    vector output(n);  // Output array
    int count[10] = {0};    // Count array for digits 0-9

    // Count occurrences of each digit at current place value
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Update count[i] to store the position of the digit in output array
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array in sorted order
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Copy sorted values back to original array
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// Main function to perform Radix Sort
void radixSort(vector& arr) {
    int maxVal = getMax(arr); // Find the maximum number to determine digit places

    // Perform Counting Sort for each digit place (1s, 10s, 100s, ...)
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

// Driver function
int main() {
    vector arr = {170, 45, 75, 90, 802, 24, 2, 66};

    cout << "Original array: ";
    for (int num : arr)
        cout << num << " ";
    cout << endl;

    radixSort(arr);

    cout << "Sorted array: ";
    for (int num : arr)
        cout << num << " ";
    cout << endl;

    return 0;
}

          

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIEZ1bmN0aW9uIHRvIGdldCB0aGUgbWF4aW11bSB2YWx1ZSBpbiB0aGUgYXJyYXkKaW50IGdldE1heChjb25zdCB2ZWN0b3I8aW50PiYgYXJyKSB7CiAgICByZXR1cm4gKm1heF9lbGVtZW50KGFyci5iZWdpbigpLCBhcnIuZW5kKCkpOwp9CgovLyBGdW5jdGlvbiB0byBwZXJmb3JtIENvdW50aW5nIFNvcnQgYmFzZWQgb24gYSBzcGVjaWZpYyBkaWdpdCBwbGFjZQp2b2lkIGNvdW50aW5nU29ydCh2ZWN0b3I8aW50PiYgYXJyLCBpbnQgZXhwKSB7CiAgICBpbnQgbiA9IGFyci5zaXplKCk7CiAgICB2ZWN0b3I8aW50PiBvdXRwdXQobik7ICAvLyBPdXRwdXQgYXJyYXkKICAgIGludCBjb3VudFsxMF0gPSB7MH07ICAgIC8vIENvdW50IGFycmF5IGZvciBkaWdpdHMgMC05CgogICAgLy8gQ291bnQgb2NjdXJyZW5jZXMgb2YgZWFjaCBkaWdpdCBhdCBjdXJyZW50IHBsYWNlIHZhbHVlCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBjb3VudFsoYXJyW2ldIC8gZXhwKSAlIDEwXSsrOwoKICAgIC8vIFVwZGF0ZSBjb3VudFtpXSB0byBzdG9yZSB0aGUgcG9zaXRpb24gb2YgdGhlIGRpZ2l0IGluIG91dHB1dCBhcnJheQogICAgZm9yIChpbnQgaSA9IDE7IGkgPCAxMDsgaSsrKQogICAgICAgIGNvdW50W2ldICs9IGNvdW50W2kgLSAxXTsKCiAgICAvLyBCdWlsZCB0aGUgb3V0cHV0IGFycmF5IGluIHNvcnRlZCBvcmRlcgogICAgZm9yIChpbnQgaSA9IG4gLSAxOyBpID49IDA7IGktLSkgewogICAgICAgIG91dHB1dFtjb3VudFsoYXJyW2ldIC8gZXhwKSAlIDEwXSAtIDFdID0gYXJyW2ldOwogICAgICAgIGNvdW50WyhhcnJbaV0gLyBleHApICUgMTBdLS07CiAgICB9CgogICAgLy8gQ29weSBzb3J0ZWQgdmFsdWVzIGJhY2sgdG8gb3JpZ2luYWwgYXJyYXkKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgIGFycltpXSA9IG91dHB1dFtpXTsKfQoKLy8gTWFpbiBmdW5jdGlvbiB0byBwZXJmb3JtIFJhZGl4IFNvcnQKdm9pZCByYWRpeFNvcnQodmVjdG9yPGludD4mIGFycikgewogICAgaW50IG1heFZhbCA9IGdldE1heChhcnIpOyAvLyBGaW5kIHRoZSBtYXhpbXVtIG51bWJlciB0byBkZXRlcm1pbmUgZGlnaXQgcGxhY2VzCgogICAgLy8gUGVyZm9ybSBDb3VudGluZyBTb3J0IGZvciBlYWNoIGRpZ2l0IHBsYWNlICgxcywgMTBzLCAxMDBzLCAuLi4pCiAgICBmb3IgKGludCBleHAgPSAxOyBtYXhWYWwgLyBleHAgPiAwOyBleHAgKj0gMTApCiAgICAgICAgY291bnRpbmdTb3J0KGFyciwgZXhwKTsKfQoKLy8gRHJpdmVyIGZ1bmN0aW9uCmludCBtYWluKCkgewogICAgdmVjdG9yPGludD4gYXJyID0gezE3MCwgNDUsIDc1LCA5MCwgODAyLCAyNCwgMiwgNjZ9OwoKICAgIGNvdXQgPDwgIk9yaWdpbmFsIGFycmF5OiAiOwogICAgZm9yIChpbnQgbnVtIDogYXJyKQogICAgICAgIGNvdXQgPDwgbnVtIDw8ICIgIjsKICAgIGNvdXQgPDwgZW5kbDsKCiAgICByYWRpeFNvcnQoYXJyKTsKCiAgICBjb3V0IDw8ICJTb3J0ZWQgYXJyYXk6ICI7CiAgICBmb3IgKGludCBudW0gOiBhcnIpCiAgICAgICAgY291dCA8PCBudW0gPDwgIiAiOwogICAgY291dCA8PCBlbmRsOwoKICAgIHJldHVybiAwOwp9Cg==

Output: 

Original array: 170 45 75 90 802 24 2 66 
Sorted array: 2 24 45 66 75 90 170 802 

Explanation:

In the above code example-

1. We start by including necessary headers: <iostream> for input/output operations, <vector> for dynamic arrays, and <algorithm> for using max_element.
2. The getMax() function helps us find the maximum element in the array, which determines the number of digits to process in Radix Sort.
3. The countingSort() function sorts the array based on a specific digit place (exp), using Counting Sort as a subroutine.
4. We initialize an output array to store sorted values and a count array of size 10 (for digits 0-9) to track occurrences of each digit.
5. We update the count array to store the positions of digits in the output array.
6. We build the output array by placing elements in sorted order according to the current digit place.
7. The sorted values are copied back to the original array.
8. The radixSort() function sorts the array using digit-wise Counting Sort, starting from the least significant digit (1s place) and moving up (10s, 100s, etc.).
9. The loop in radixSort ensures we sort based on all digit places until the maximum value is fully processed.
10. In main, we declare a vector with sample values and print the original array.
11. We call radixSort to sort the array using Radix Sort.
12. Finally, we print the sorted array, showing the transformation from an unsorted to a sorted list.

Time & Space Complexity Analysis Of Radix Sort

Where:

• n = Number of elements in the array
• k = Number of digits in the largest number

Since k is relatively small compared to nnn in most cases, Radix Sort runs in near-linear time and is efficient for large datasets with uniform-length numbers.

Advantages Of Radix Sort

Some common advantages of radix sort are:

1. Linear Time Complexity – Radix Sort runs in O(nk), making it faster than comparison-based sorting algorithms like QuickSort and MergeSort for fixed-length integers.
   
   
2. No Comparisons Needed – Unlike traditional sorting algorithms, Radix Sort doesn't rely on element comparisons, which can be beneficial in certain applications.
   
   
3. Stable Sorting Algorithm – It maintains the relative order of elements with equal values, which is useful when sorting objects with multiple attributes.
   
   
4. Efficient for Large Data – It is well-suited for sorting large numbers, such as ZIP codes, phone numbers, and IP addresses, where digit-based sorting is advantageous.
   
   
5. Parallel Processing Possible – Since each digit is processed independently, Radix Sort can be easily parallelized for performance improvements.

Disadvantages Of Radix Sort

Some common disadvantages of radix sort are:

1. Extra Space Requirement – Radix Sort requires additional space for auxiliary arrays (buckets), leading to a space complexity of O(n + k), which can be inefficient for memory-constrained systems.
   
   
2. Limited to Fixed-Length Numbers – The algorithm is primarily effective for numbers and fixed-length strings but struggles with variable-length data.
   
   
3. Not Always Faster Than Comparison-Based Sorts – When the number of digits k is large, Radix Sort may perform worse than QuickSort or MergeSort, which have an average time complexity of O(nlogn).
   
   
4. Digit-Based Dependency – The number of sorting passes depends on the number of digits in the largest number, which can make it inefficient for extremely large numbers.
   
   
5. Cache Inefficiency – Since Radix Sort operates using multiple passes and auxiliary storage, it may not be as cache-friendly as in-place sorting algorithms like QuickSort.

Applications Of Radix Sort Algorithm

Given below are the key applications of radix sort algorithm:

1. Sorting Large Numbers – Radix Sort is widely used for sorting large integers, such as bank account numbers, phone numbers, and postal codes, where digit-based sorting is efficient.
   
   
2. Processing Fixed-Length Strings – It can be adapted for sorting fixed-length strings (e.g., DNA sequences, product codes, and serial numbers) by treating characters as digits.
   
   
3. IP Address Sorting – Since IP addresses (IPv4) consist of four numerical segments, Radix Sort can efficiently sort them by processing each segment separately.
   
   
4. Suffix Array Construction – In string processing and text indexing, Radix Sort helps construct suffix arrays efficiently, particularly in applications like pattern matching and data compression.
   
   
5. Digital Circuit Applications – Radix Sort is used in hardware implementations for digital signal processing (DSP) and sorting data in embedded systems.
   
   
6. Geographical Data Processing – It is useful for sorting geolocation data, such as latitude and longitude values, in spatial databases and mapping systems.
   
   
7. Big Data and Distributed Systems – Due to its non-comparative nature, Radix Sort is employed in distributed computing environments where massive datasets need efficient sorting.
   
   
8. Computer Graphics and Image Processing – It is used in rendering pipelines to sort pixel intensities, object depths (Z-buffer sorting), and texture data.

Conclusion

Radix Sort is a powerful, non-comparative sorting algorithm that efficiently sorts numbers and fixed-length data by processing digits sequentially. With a time complexity of O(nk), it outperforms comparison-based sorting algorithms like QuickSort and MergeSort in scenarios where k (the number of digits) is significantly smaller than logn. Its stability, predictable performance, and efficiency in sorting large datasets make it valuable for applications such as numerical sorting, IP address management, and text processing.

However, Radix Sort comes with trade-offs, including higher space complexity and limited applicability to variable-length data. While it excels in specific use cases, comparison-based sorting algorithms remain preferable for general-purpose sorting due to their in-place nature and versatility. By understanding its strengths and limitations, we can leverage Radix Sort effectively in situations where its unique advantages shine.

Frequently Asked Questions

Q. Why is Radix Sort considered a non-comparative sorting algorithm?

Radix Sort does not compare elements directly to determine their order. Instead, it processes numbers digit by digit using a stable sorting technique like Counting Sort. This makes it fundamentally different from comparison-based algorithms like QuickSort and MergeSort.

Q. What is the difference between LSD (Least Significant Digit) and MSD (Most Significant Digit) Radix Sort?

• LSD Radix Sort processes numbers starting from the rightmost (least significant) digit and moves left. It is the most commonly used approach.
• MSD Radix Sort starts sorting from the leftmost (most significant) digit and moves right, making it more suitable for sorting variable-length numbers.

Q. When is Radix Sort more efficient than QuickSort or MergeSort?

Radix Sort is more efficient when sorting large datasets where the number of digits kkk is much smaller than log⁡n\log nlogn. It runs in linear time O(nk), making it faster than comparison-based sorting algorithms, which run in O(nlogn).

Q. Why is Radix Sort considered a stable sorting algorithm?

Radix Sort maintains the relative order of elements with the same value. Since it processes digits from least to most significant (or vice versa), elements with equal keys remain in their original order after sorting.

Q. What are the main drawbacks of Radix Sort?

Radix Sort requires extra space for auxiliary arrays, making it less space-efficient than in-place sorting algorithms like QuickSort. Additionally, it is limited to sorting fixed-length numerical or string data and may not be efficient for very large digit counts.

Suggested Reads:

1. Difference Between Hashing And Encryption Decoded
2. 53 Frequently Asked Linked List Interview Questions With Answers 2024
3. Data Structure Interview Questions For 2024 [With Detailed Answers]
4. Tree Topology | Advantages & Disadvantages In Computer Network
5. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions