Radix Sort

Radix Sort Algorithm

In the previous tutorial, we learned about Counting Sort. Counting Sort is amazing, but it fails when the range of numbers is very large (like 1 to 1,000,000) because it requires too much memory.

Radix Sort fixes this exact problem! It uses the idea of buckets but processes numbers one digit at a time.

1. How Does Radix Sort Work?

Radix Sort works exactly like how you might sort words alphabetically: first by the last letter, then the middle letter, and finally the first letter.

With numbers, it processes digits from right to left:

1. First, sort the numbers based only on their 1s place (the last digit).
2. Next, sort the numbers based only on their 10s place.
3. Next, sort based on the 100s place.
4. Repeat until you have processed the longest number in the list.

By the time you finish the final digit, the entire array is magically sorted!

2. A Step-by-Step Example

Let's sort this array of numbers: [42, 17, 45, 22, 19]

Step 1: Sort by the 1s Place Look ONLY at the last digits: 42, 17, 45, 22, 19.

• We put them in order based on those highlighted numbers.
• The array becomes: [42, 22, 45, 17, 19].
• (Notice how 42 comes before 22 because 42 was listed first originally. This is called a "Stable" sort).

Step 2: Sort by the 10s Place Now look ONLY at the first digits: 42, 22, 45, 17, 19.

• We put them in order based on those highlighted numbers.
• The array becomes: [17, 19, 22, 42, 45].

The longest number only had two digits, so we are done. The array is sorted!

Radix Sort: Processing from the rightmost digit to the leftmost digit.

3. Radix Sort Code Example

Here is a beginner-friendly Python implementation. Instead of using complicated math, we will create 10 simple "buckets" (lists) representing the digits 0 through 9. We place numbers in their respective buckets for each digit place!

def radix_sort(arr):
    # 1. Find the maximum number to know how many digits we have
    max_num = max(arr)
    # Initialize the place value to 1 (1s place)
    place = 1
    # 2. Run the loop for each digit place (1s, 10s, 100s...)
    while max_num // place > 0:
        # Create 10 empty buckets (for digits 0 through 9)
        buckets = [[] for _ in range(10)]
        # 3. Put each number into the correct bucket based on the current digit
        for num in arr:
            digit = (num // place) % 10
            buckets[digit].append(num)
        # 4. Rebuild the array by emptying the buckets in order!
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
        # Move to the next place value (1s becomes 10s, 10s becomes 100s)
        place *= 10
    return arr

numbers = [42, 17, 45, 22, 19]
print("Original:", numbers)
print("Sorted:", radix_sort(numbers))

4. Time and Space Complexity

• Time Complexity: O(d * (n + b)).
  • d is the number of digits in the maximum element.
  • n is the number of elements in the array.
  • b is the base of the numbering system (10 for decimal numbers). It is incredibly fast and avoids the O(n²) trap of Bubble and Selection sort!
• Space Complexity: O(n + b). It requires extra memory to hold the "buckets" while sorting.