Radix Sort Algorithm

Radix Sort is a non-comparative integer sorting algorithm that sorts elements by processing individual digits. It processes the digits from the least significant digit (LSD) to the most significant digit (MSD), grouping and sorting numbers based on each digit’s position using a stable sorting algorithm like Counting Sort. Radix Sort is especially efficient when the range of digits is limited and the number of digits (d) is small compared to the number of elements (n).

How It Works:

1. Look at the Unit Place (1s place)
   • Group and sort the numbers based on their last digit.
2. Then Look at the Tens Place (10s place)
   • Sort again, but this time based on the second last digit.
3. Then Hundreds, Thousands…
   • Continue this process until the most significant digit (leftmost).

Example of Radix Sort

Let’s sort the following list of numbers:
Input: [170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Sort by Unit Place (1s digit)

Look only at the last digit of each number:

170 → 0 

45 → 5 

75 → 5 

90 → 0 

802 → 2 

24 → 4 

2   → 2 

66 → 6

 Now sort based on these digits:
→ [170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by Tens Place (10s digit)

Now look at the second-last digit:

170 → 7 

90 → 9 

802 → 0 

2   → 0 

24 → 2 

45 → 4 

75 → 7 

66 → 6

Sort based on these:
→ [802, 2, 24, 45, 66, 170, 75, 90]

 Step 3: Sort by Hundreds Place (100s digit)

Now look at the hundreds place:

802 → 8 

2   → 0 

24 → 0 

45 → 0 

66 → 0 

170 → 1 

75 → 0 

90 → 0

• Sort based on these:
  → [2, 24, 45, 66, 75, 90, 170, 802]

Final Sorted Output:

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

Radix sort Python code:

function radixSort(arr):

    maxVal = max(arr)

    exp = 1

    while maxVal // exp > 0:

        countingSortByDigit(arr, exp)

        exp *= 10

Time Complexity of Radix Sort

What Do the Terms Mean?

• n = Number of elements to sort
• d = Number of digits in the largest number
• k = Range of digits (usually 10 for decimal system: 0 to 9)