Radix Sort – Learn Step-by-Step with GoNimbus

Sorting is a key concept in Data Structures and Algorithms (DSA). Among all the sorting techniques, Radix Sort stands out for its non-comparative and digit-based approach. Let’s explore how this powerful algorithm works, step by step.

---

🔍 What is Radix Sort?

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits.
It starts with the least significant digit (LSD) — the rightmost one — and gradually moves toward the most significant digit (MSD).

Instead of comparing elements directly, Radix Sort distributes numbers into buckets (0–9) based on the digit currently being processed.

---

⚙️ How Radix Sort Works

Here’s how the algorithm proceeds:

1. Start with the least significant digit (rightmost digit).
2. Place each number into the correct bucket (0–9) based on that digit.
3. Collect all numbers from the buckets in order and put them back into the array.
4. Move to the next digit to the left and repeat the process.
5. Continue until all digits have been processed — and the array is sorted!

💡 Note: Radix Sort only works with non-negative integers and relies on stable sorting to maintain the relative order of equal elements.

---

🧩 Understanding Stability in Sorting

A sorting algorithm is stable if it preserves the order of equal elements before and after sorting.
In Radix Sort, stability is crucial — because when sorting digit by digit, the previous order must remain intact for the final output to be correct.

Example:
If we have two numbers 25 and 45 with the same last digit 5, and 25 comes first, then 25 should still come before 45 after sorting by the next digit.

---

🧠 Manual Example of Radix Sort

Let’s manually go through an example:

myArray = [33, 45, 40, 25, 17, 24]

Step 1: Sort by least significant digit

radixArray = [ [40], [], [], [33], [24], [45, 25], [], [17], [], [] ]

Step 2: Rebuild array after first pass

myArray = [40, 33, 24, 45, 25, 17]

Step 3: Sort by next digit (tens place)

radixArray = [ [], [17], [24, 25], [33], [40, 45], [], [], [], [], [] ]

Final Sorted Array:

[17, 24, 25, 33, 40, 45]

---

💻 Python Implementation

Here’s how you can implement Radix Sort in Python:

myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)

radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(myArray)
exp = 1

while maxVal // exp > 0:
    while len(myArray) > 0:
        val = myArray.pop()
        radixIndex = (val // exp) % 10
        radixArray[radixIndex].append(val)

    for bucket in radixArray:
        while len(bucket) > 0:
            val = bucket.pop()
            myArray.append(val)

    exp *= 10

print("Sorted array:", myArray)

---

🧮 Radix Sort with Bubble Sort

You can also use Bubble Sort as the stable sorting method for each digit pass:

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

def radixSortWithBubbleSort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        radixArray = [[], [], [], [], [], [], [], [], [], []]
        for num in arr:
            radixIndex = (num // exp) % 10
            radixArray[radixIndex].append(num)
        for bucket in radixArray:
            bubbleSort(bucket)
        i = 0
        for bucket in radixArray:
            for num in bucket:
                arr[i] = num
                i += 1
        exp *= 10

myArray = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", myArray)
radixSortWithBubbleSort(myArray)
print("Sorted array:", myArray)

---

⏱️ Time Complexity of Radix Sort

Let:

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

Then,
👉 Time Complexity: O(n × k)
👉 Space Complexity: O(n + k)

Best Case: O(n) (few digits, many numbers)
Worst Case: O(n × k) (large digits per number)
Stable: ✅ Yes

---

🚀 When to Use Radix Sort

✅ When sorting large sets of integers
✅ When stability matters
✅ When numbers have limited digits

Avoid using it for:
❌ Floating-point numbers
❌ Negative values (without modification)
❌ Comparisons of non-numeric data

---

💬 In Summary

Radix Sort offers:

• Fast sorting for integer data
• Predictable performance
• A clear example of non-comparative sorting
• A great foundation to understand bucket-based sorting algorithms

---

🌐 Start Your DSA Journey with GoNimbus

At GoNimbus, we make learning DSA interactive and beginner-friendly.
Explore our visual tutorials, run step-by-step simulations, and build a rock-solid foundation in algorithms like Radix Sort, Merge Sort, and Quick Sort.

🎯 Next Up: [Counting Sort →] or [Back to Sorting Algorithms Hub →]

---