Radix Sort Algorithm in DSA Python

Mental Model

Sort numbers by processing digits from least to most significant, grouping them by each digit place.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until fully sorted.

Array: [170, 45, 75, 90, 802, 24, 2, 66]
Buckets for digit place:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

Input: list: [170, 45, 75, 90, 802, 24, 2, 66]

Goal: Sort the list in ascending order using radix sort by processing digits from right to left.

Step 1: Sort numbers by least significant digit (ones place)

Buckets:
0: [170, 90]
1: []
2: [802, 2]
3: []
4: [24]
5: [45, 75]
6: [66]
7: []
8: []
9: []
Reassembled array: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Grouping by ones digit organizes numbers partially to prepare for next digit sorting.

Step 2: Sort numbers by second least significant digit (tens place)

Buckets:
0: [802, 2]
1: []
2: [24]
3: []
4: []
5: [45]
6: [66]
7: [170, 75]
8: []
9: [90]
Reassembled array: [802, 2, 24, 45, 66, 170, 75, 90]

Why: Sorting by tens digit refines order further, moving closer to fully sorted.

Step 3: Sort numbers by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
2: []
3: []
4: []
5: []
6: []
7: []
8: [802]
9: []
Reassembled array: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Sorting by hundreds digit completes the sorting process for these numbers.

Result:

Final sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

Annotated Code

DSA Python

class RadixSort:
    def __init__(self, arr):
        self.arr = arr

    def counting_sort(self, exp):
        n = len(self.arr)
        output = [0] * n
        count = [0] * 10

        # Count occurrences of digits
        for i in range(n):
            index = (self.arr[i] // exp) % 10
            count[index] += 1

        # Change count[i] so it contains actual position
        for i in range(1, 10):
            count[i] += count[i - 1]

        # Build output array
        i = n - 1
        while i >= 0:
            index = (self.arr[i] // exp) % 10
            output[count[index] - 1] = self.arr[i]
            count[index] -= 1
            i -= 1

        # Copy output to arr
        for i in range(n):
            self.arr[i] = output[i]

    def sort(self):
        max1 = max(self.arr) if self.arr else 0
        exp = 1
        while max1 // exp > 0:
            self.counting_sort(exp)
            exp *= 10


if __name__ == '__main__':
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    sorter = RadixSort(arr)
    sorter.sort()
    print(' -> '.join(str(x) for x in sorter.arr) + ' -> null')

index = (self.arr[i] // exp) % 10

Extract digit at current exponent place for counting

count[index] += 1

Count how many times each digit appears

count[i] += count[i - 1]

Accumulate counts to get positions in output

output[count[index] - 1] = self.arr[i]

Place element in correct position in output array

self.arr[i] = output[i]

Copy sorted output back to original array

while max1 // exp > 0:

Repeat sorting for each digit place until max digit processed

Output

2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k=10 for digits; because it sorts by each digit using counting sort.

Space: O(n + k) for output and count arrays used in counting sort.

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit sizes since it sorts in linear time relative to number of elements.

Edge Cases

Empty list

No sorting happens, output remains empty.

DSA Python

max1 = max(self.arr) if self.arr else 0

List with one element

Sorting runs but array remains unchanged.

DSA Python

while max1 // exp > 0:

All elements are the same

Sorting runs but array remains unchanged.

DSA Python

while max1 // exp > 0:

When to Use This Pattern

When you need to sort numbers efficiently by digits without comparisons, especially with fixed digit lengths, reach for radix sort because it sorts in linear time by processing digits one at a time.

Common Mistakes

Mistake: Not using stable counting sort for each digit, causing incorrect final order.
Fix: Use counting sort that processes elements from right to left to maintain stability.

Summary

Sorts numbers by processing digits from least to most significant using stable counting sort.

Use when sorting integers with fixed digit lengths for efficient linear time sorting.

The key insight is sorting by each digit place preserves order and leads to fully sorted array.

Practice

1. What is the main idea behind the Radix Sort algorithm?

easy

A. Use a pivot to partition the list and sort partitions separately

B. Compare each element with every other element and swap if needed

C. Divide the list into halves and sort each half recursively

D. Sort numbers digit by digit starting from the least significant digit

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing individual digits starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Other options describe Bubble Sort, Merge Sort, and Quick Sort, which are different algorithms.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option D

4. Quick Check:

   Radix Sort = Sort by digits from right to left [OK]

Hint: Radix Sort processes digits from right to left [OK]

Common Mistakes:

• Confusing Radix Sort with comparison-based sorts
• Thinking it sorts from most significant digit first
• Assuming it uses pivot or recursion

2. Which of the following is the correct way to initialize a list of empty buckets for Radix Sort in Python?

easy

A. buckets = [[]] * 10

B. buckets = [[] for _ in range(10)]

C. buckets = [0] * 10

D. buckets = list(range(10))

Solution

1. Step 1: Understand bucket initialization

   We need 10 separate empty lists (buckets) for digits 0-9, so list comprehension creates independent lists.

2. Step 2: Analyze options

   buckets = [[]] * 10 creates 10 references to the same list, causing bugs. buckets = [0] * 10 creates integers, not lists. buckets = list(range(10)) creates a list of numbers, not buckets.

3. Final Answer:

   buckets = [[] for _ in range(10)] -> Option B

4. Quick Check:

   Independent empty lists = list comprehension [OK]

Hint: Use list comprehension for independent empty lists [OK]

Common Mistakes:

• Using [[]] * 10 causes all buckets to reference the same list
• Initializing buckets with zeros instead of lists
• Confusing range with list of empty lists

3. What will be the output of the following Python code snippet implementing one pass of Radix Sort on the least significant digit?

arr = [170, 45, 75, 90, 802, 24, 2, 66]
buckets = [[] for _ in range(10)]
for num in arr:
    digit = num % 10
    buckets[digit].append(num)
result = []
for bucket in buckets:
    result.extend(bucket)
print(result)

medium

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

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

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

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

Solution

1. Step 1: Group numbers by least significant digit

   Digits are: 170(0), 45(5), 75(5), 90(0), 802(2), 24(4), 2(2), 66(6). Buckets: 0:[170,90], 2:[802,2], 4:[24], 5:[45,75], 6:[66].

2. Step 2: Concatenate buckets in order 0 to 9

   Result list is [170, 90] + [] + [802, 2] + [] + [24] + [45, 75] + [66] + [] + [] + [] = [170, 90, 802, 2, 24, 45, 75, 66].

3. Final Answer:

   [170, 90, 802, 2, 24, 45, 75, 66] -> Option C

4. Quick Check:

   Sorted by last digit = [170, 90, 802, 2, 24, 45, 75, 66] [OK]

Hint: Group by digit, then join buckets in digit order [OK]

Common Mistakes:

• Mixing digit extraction (using // instead of %)
• Not preserving order inside buckets
• Concatenating buckets in wrong order

4. The following code attempts to perform Radix Sort but has a bug. What is the error?

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        buckets = [[]] * 10
        for num in arr:
            index = (num // exp) % 10
            buckets[index].append(num)
        arr = []
        for bucket in buckets:
            arr.extend(bucket)
        exp *= 10
    return arr

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

medium

A. Using buckets = [[]] * 10 causes all buckets to reference the same list

B. The loop condition should be while max_num % exp > 0

C. The digit extraction formula is incorrect

D. The function does not return the sorted array

Solution

1. Step 1: Identify bucket initialization issue

   buckets = [[]] * 10 creates 10 references to the same list, so appending to one bucket appends to all.

2. Step 2: Check other parts

   Loop condition and digit extraction are correct. The function returns arr properly.

3. Final Answer:

   Using buckets = [[]] * 10 causes all buckets to reference the same list -> Option A

4. Quick Check:

   Bucket initialization = [[] for _ in range(10)] [OK]

Hint: Avoid [[]]*10; use list comprehension for buckets [OK]

Common Mistakes:

• Using [[]]*10 instead of list comprehension
• Changing loop condition incorrectly
• Misunderstanding digit extraction

5. You want to sort the list [329, 457, 657, 839, 436, 720, 355] using Radix Sort. After sorting by the least significant digit (units place), what will the list look like?

hard

A. [720, 355, 436, 457, 657, 329, 839]

B. [329, 720, 436, 457, 657, 839, 355]

C. [720, 329, 436, 839, 457, 657, 355]

D. [355, 720, 436, 329, 457, 657, 839]

Solution

1. Step 1: Extract least significant digit of each number

   329(9), 457(7), 657(7), 839(9), 436(6), 720(0), 355(5).

2. Step 2: Group numbers by last digit and concatenate in digit order 0-9

   Digits 0:[720], 5:[355], 6:[436], 7:[457, 657], 9:[329, 839]. Concatenate: [720, 355, 436, 457, 657, 329, 839].

3. Final Answer:

   [720, 355, 436, 457, 657, 329, 839] -> Option A

4. Quick Check:

   Sorted by units digit = [720, 355, 436, 457, 657, 329, 839] [OK]

Hint: Sort by last digit, keep order inside groups [OK]

Common Mistakes:

• Mixing digit extraction with division instead of modulo
• Not preserving order of numbers with same digit
• Concatenating buckets in wrong digit order