Radix Sort Algorithm in DSA Python - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know max digits

↓

Set digit place = 1 (units)

↓

While digit place <= max digits

↓

Distribute numbers into buckets by digit

↓

Collect numbers from buckets back to list

↓

Increase digit place by factor 10

↓

Repeat until all digits processed

↓

Sorted list ready

Radix sort processes numbers digit by digit from least to most significant, grouping by digit and collecting back repeatedly until fully sorted.

Execution Sample

DSA Python

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

Sorts the array by processing digits from least significant to most significant using counting sort as a subroutine.

Execution Table

Step	Operation	Digit Place (exp)	Buckets (0-9)	List After Collection	Visual State
1	Find max number	-	-	-	[170, 45, 75, 90, 802, 24, 2, 66]
2	Digit place = 1 (units)	1	[[170, 90], [], [802, 2], [], [24], [45, 75], [66], [], [], []]	[170, 90, 802, 2, 24, 45, 75, 66]	Buckets show numbers grouped by units digit
3	Digit place = 10 (tens)	10	[[802, 2], [], [24], [], [45], [], [66], [170, 75], [], [90]]	[802, 2, 24, 45, 66, 170, 75, 90]	Buckets show numbers grouped by tens digit
4	Digit place = 100 (hundreds)	100	[[2, 24, 45, 66, 75, 90], [170], [], [], [], [], [], [], [802], []]	[2, 24, 45, 66, 75, 90, 170, 802]	Buckets show numbers grouped by hundreds digit
5	Digit place = 1000 (thousands)	1000	[[2, 24, 45, 66, 75, 90, 170, 802], [], [], [], [], [], [], [], [], []]	[2, 24, 45, 66, 75, 90, 170, 802]	No change, sorting complete
6	Exit loop	-	-	-	max_num // exp = 0, sorting done

💡 max_num // exp = 0 at exp=10000, loop ends, list fully sorted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
arr	[170, 45, 75, 90, 802, 24, 2, 66]	[170, 90, 802, 2, 24, 45, 75, 66]	[802, 2, 24, 45, 66, 170, 75, 90]	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]
exp	1	10	100	1000	10000	10000
max_num	802	802	802	802	802	802

Key Moments - 3 Insights

Why do we start sorting from the least significant digit (units place)?

Because radix sort relies on stable sorting at each digit place, starting from the least significant digit ensures that the order of digits processed earlier is preserved, as shown in execution_table rows 2 to 4.

What happens when the digit place (exp) exceeds the maximum number's digits?

When exp becomes larger than the max number (see step 6), max_num // exp equals zero, so the loop stops, meaning all digits have been processed and the list is sorted.

Why do we use buckets for digits 0 to 9 in each step?

Buckets group numbers by the current digit being processed, allowing us to collect them in order and maintain stability. This is visible in the 'Buckets' column in execution_table steps 2 to 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the list after collecting from buckets?

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

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

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

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

💡 Hint

Check the 'List After Collection' column at step 3 in execution_table.

At which step does the digit place (exp) become 100?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Digit Place (exp)' column in execution_table to find when exp is 100.

If the maximum number was 99 instead of 802, at which step would the loop stop?

A After processing digit place 10 (tens)

B After processing digit place 100 (hundreds)

C After processing digit place 1 (units)

D After processing digit place 1000 (thousands)

💡 Hint

Recall that the loop stops when max_num // exp == 0; with max_num=99, exp=100 causes loop to end.

Concept Snapshot

Radix Sort Algorithm:
- Sorts numbers digit by digit from least to most significant
- Uses buckets (0-9) to group numbers by current digit
- Collects numbers from buckets to form new list each pass
- Repeats until all digit places processed
- Requires stable sorting at each digit
- Efficient for sorting integers with known digit length

Full Transcript

Radix sort works by sorting numbers starting from the least significant digit (units place) and moving to more significant digits (tens, hundreds, etc.). At each digit place, numbers are grouped into buckets based on the digit at that place. Then, numbers are collected back from the buckets in order, preserving stability. This process repeats with increasing digit places until the highest digit of the largest number is processed. The execution table shows the list state and bucket contents at each step, and the variable tracker shows how the array and digit place change. The loop ends when the digit place exceeds the maximum number's digits, ensuring the list is fully sorted.

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