Radix Sort Algorithm with Solved Example

Radix sort is a non-comparative sorting algorithm that sorts elements digit by digit starting from least significant digit to most significant digit. Unlike other sorting methods like Quick Sort or Merge Sort that compare elements, Radix Sort groups numbers based on their digit places — such as units, tens, hundreds, etc. It commonly uses Counting Sort or, less frequently, Bucket Sort, as a stable intermediate sorting technique for each digit pass.

This makes Radix Sort very useful when:

• You are sorting large amounts of numbers
• The range of numbers is big
• You want a stable and predictable time complexity

What is Radix Sort?

Radix Sort is a technique that sorts numbers digit-by-digit, starting from the least significant digit (LSD) (units place) to the most significant digit (MSD) (hundreds/thousands place).

It places numbers into buckets (0–9) based on the current digit, rearranges them, and repeats the process for the next digit.

Key Idea: Sort numbers based on digits, not by comparing whole numbers.

How Radix Sort Works (Step-by-Step)

Let’s understand with a simple example:

Suppose we want to sort:

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

Step 1: Sort by the units digit (1’s place):

• Numbers are placed in buckets according to the last digit.
• After collecting them back, the list becomes:

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

Step 2: Sort by the tens digit (10’s place):

Using the tens digit, we get:

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

Step 3: Sort by the hundreds digit (100’s place):

Using the hundreds place:

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

Now the list is sorted.

Algorithm of Radix Sort (LSD Version)

1. Find the maximum number to know the number of digits.
2. For each digit place (1’s, 10’s, 100’s, …):
   • Apply Counting Sort on that digit.
3. Repeat until the highest place value is processed.

This ensures numbers are sorted correctly.

Time Complexity of Radix Sort

Here,

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

Radix sort is faster when k is small.

Space Complexity of Radix Sort

Here,

• n = number of elements
• k = number of possible digit values (10 for decimal digits → treated as constant)
• So practically:
  Best, Average, Worst = O(n)

Advantages of Radix Sort

1. Very fast for large datasets
   Works efficiently when all numbers have a similar number of digits.
2. Not comparison-based
   It avoids O(n log n) limits of comparison sorts and can achieve linear time.
3. Stable sorting
   Equal elements maintain their original order (important for records).
4. Great performance on integers and fixed-length strings
   Sorting digit-by-digit makes it ideal for numeric data.
5. Predictable performance
   Time complexity is always O(n × k), with no worst-case degradation like Quick Sort.

Disadvantages of Radix Sort

1. Uses extra memory
   Requires O(n + k) additional space due to buckets and output array.
2. Not suitable for all data types
   Works best for integers or strings; not good for floating or complex custom types.
3. Implementation is more complex
   Harder to code compared to simple algorithms like Bubble Sort or Insertion Sort.
4. Inefficient if digit range is large
   If k (digit range) becomes large, performance decreases.
5. Slower for small datasets
   Overhead of bucket creation makes it slower compared to simpler algorithms for small inputs.

Applications of Radix Sort

1. Sorting large integer datasets
   Widely used where huge numeric lists need fast sorting.
2. Sorting strings in lexicographic order
   MSD Radix Sort works well for fixed-length strings (like codes or IDs).
3. Used in digital systems and hardware implementations
   Excellent for sorting binary numbers efficiently using bit operations.
4. Database indexing and searching
   Helps in organizing numeric keys for fast retrieval.
5. Telephone directory or postal code sorting
   Since values are numeric and fixed-length, Radix Sort works very efficiently.