Radix Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know max digits

↓

For each digit place from LSD to MSD

↓

Place numbers into buckets by current digit

↓

Collect numbers from buckets in order

↓

Repeat for next digit place

↓

Sorted array obtained

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

Execution Sample

DSA C++

void radixSort(int arr[], int n) {
  int max = *max_element(arr, arr + n);
  for (int exp = 1; max / exp > 0; exp *= 10) {
    countSort(arr, n, exp);
  }
}

Sorts 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)	Array State After Collection	Notes
1	Find max number	-	-	-	Max number is 802
2	Process digit place	1 (units)	[170, 90, 802, 2, 24, 45, 75, 66]	[170, 90, 802, 2, 24, 45, 75, 66]	Bucketed by units digit
3	Process digit place	10 (tens)	[802, 2, 24, 45, 66, 170, 75, 90]	[802, 2, 24, 45, 66, 170, 75, 90]	Bucketed by tens digit
4	Process digit place	100 (hundreds)	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]	Bucketed by hundreds digit
5	Check next digit place	1000	-	-	max / 1000 > 0? No, stop sorting

💡 No more digits to process, array is sorted

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
arr	[170, 45, 75, 90, 802, 24, 2, 66]	[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]
max	N/A	802	802	802	802	802
exp	N/A	1	10	100	1000	1000

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 steps 2 to 4 in the execution_table.

What happens if the max number has fewer digits than others?

Digits beyond the max number's length are treated as zero, so those numbers go into the zero bucket. This is why in step 4, numbers with no hundreds digit are placed correctly.

Why do we stop when exp (digit place) exceeds max number?

Because no more digits exist beyond the max number's length, so further passes won't change the order. Step 5 shows this check and stops the sorting.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the array state after collecting from buckets?

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

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

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

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

💡 Hint

Check the 'Array State After Collection' column in execution_table row for step 2

At which digit place does the array become fully sorted?

A 100 (hundreds)

B 10 (tens)

C 1 (units)

D 1000 (thousands)

💡 Hint

Look at the final array state after step 4 in execution_table

If the max number was 99 instead of 170, how many digit places would radix sort process?

A 1

B 2

C 3

D 4

💡 Hint

Radix sort processes digits until exp > max; 99 has 2 digits, so steps for exp=1 and exp=10

Concept Snapshot

Radix Sort Algorithm:
- Sorts numbers digit by digit from least to most significant
- Uses stable sorting (like counting sort) at each digit
- Stops when digit place exceeds max number's digits
- Efficient for sorting integers with known digit length
- Time complexity: O(d*(n+b)) where d=digits, n=array size, b=bucket count

Full Transcript

Radix sort finds the maximum number to determine how many digits to process. It sorts the array by each digit place starting from the least significant digit (units), placing numbers into buckets based on the current digit. After collecting numbers from buckets, it moves to the next digit place (tens, hundreds, etc.). This repeats until all digit places are processed, resulting in a sorted array. The process preserves order by using stable sorting at each step. The example array is sorted in three passes for units, tens, and hundreds digits. The algorithm stops when the digit place exceeds the maximum number's digit length.