Radix Sort Algorithm in DSA Go - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know digit count

↓

Start with least significant digit

↓

Distribute numbers into buckets by digit

↓

Collect numbers from buckets in order

↓

Move to next significant digit

↓

Repeat until all digits processed

↓

Sorted array

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

Execution Sample

DSA Go

arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
max := 802
digit := 1
for max/digit > 0 {
  // distribute and collect by digit
  digit *= 10
}

Sorts the array by processing each digit place from least to most significant.

Execution Table

Step	Operation	Digit Place	Buckets (0-9)	Array After Collection	Visual State
1	Find max number	-	-	-	[170, 45, 75, 90, 802, 24, 2, 66]
2	Distribute by 1's digit	1 (units)	[[170, 90], [], [802, 2], [], [24], [45, 75], [66], [], [], []]	[170, 90, 802, 2, 24, 45, 75, 66]	Buckets show numbers grouped by units digit
3	Distribute by 10's digit	10 (tens)	[[802, 2], [], [24], [], [45], [], [66], [170, 75], [], [90]]	[802, 2, 24, 45, 66, 170, 75, 90]	Buckets show numbers grouped by tens digit
4	Distribute by 100's digit	100 (hundreds)	[[2, 24, 45, 66, 75, 90], [170], [], [], [], [], [], [], [802], []]	[2, 24, 45, 66, 75, 90, 170, 802]	Buckets show numbers grouped by hundreds digit
5	Check next digit (1000's)	1000	[[], [], [], [], [], [], [], [], [], []]	[2, 24, 45, 66, 75, 90, 170, 802]	No more digits, sorting complete

💡 No more digits to process as max/digit <= 0, sorting finished

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	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]
digit	1	10	100	1000	1000
max	802	802	802	802	802

Key Moments - 3 Insights

Why do we start sorting from the least significant digit, not the most significant?

Starting from the least significant digit ensures stable sorting at each step, preserving order from previous digits as shown in steps 2 and 3 where the array order refines progressively.

What happens if a digit place has no numbers in some buckets?

Empty buckets simply mean no numbers have that digit; they are skipped during collection, as seen in step 3 where some buckets are empty but the array collects numbers in order.

Why does the sorting stop after processing the highest digit of the max number?

Because beyond the highest digit place, all digits are zero, so no further changes occur, as shown in step 5 where no new distribution happens and sorting completes.

Visual Quiz - 3 Questions

Look at the execution table at Step 3, what is the array after collection?

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

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

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

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

💡 Hint

Check the 'Array After Collection' column for Step 3 in the execution_table.

At which step does the digit place change from 10 to 100?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Digit Place' column in the execution_table to see when it changes to 100.

If the max number was 99 instead of 802, how many digit places would the algorithm process?

A 1

B 3

C 2

D 4

💡 Hint

Refer to the 'max' variable in variable_tracker and how digit places relate to max/digit > 0.

Concept Snapshot

Radix Sort processes numbers digit by digit from least to most significant.
It uses buckets (0-9) to group numbers by current digit.
After distributing, numbers are collected in order.
Repeat for each digit until max digit processed.
Stable sorting at each step preserves order.
Efficient for sorting integers with known digit length.

Full Transcript

Radix Sort works by sorting numbers starting from the least significant digit to the most significant digit. First, it finds the maximum number to know how many digits to process. Then, for each digit place (units, tens, hundreds, etc.), it distributes numbers into buckets based on that digit. After distribution, it collects numbers from buckets in order, forming a partially sorted array. This process repeats for each digit place until all digits of the maximum number are processed. The sorting stops when no more digits remain. This method ensures stable sorting and efficiently sorts integers by digit grouping.