Radix Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know max digits

↓

For each digit from LSD to MSD

↓

Place numbers into buckets by current digit

↓

Collect numbers from buckets in order

↓

Repeat for next digit

↓

Sorted array ready

Radix sort processes digits from least to most significant, grouping numbers by each digit, then collecting them back in order, repeating until fully sorted.

Execution Sample

DSA Javascript

function radixSort(arr) {
  let max = Math.max(...arr);
  let exp = 1;
  while (Math.floor(max / exp) > 0) {
    arr = countingSortByDigit(arr, exp);
    exp *= 10;
  }
  return arr;
}

Sorts an array of numbers by processing each digit from least significant to most significant using counting sort.

Execution Table

Step	Operation	Current Digit (exp)	Buckets (0-9)	Array After Collection	Visual State
1	Find max number	-	-	-	[170, 45, 75, 90, 802, 24, 2, 66]
2	Process digit exp=1 (units place)	1	0: 170, 90 1: 2: 802, 2 3: 4: 24 5: 45, 75 6: 66 7: 8: 9:	[170, 90, 802, 2, 24, 45, 75, 66]	[170, 90, 802, 2, 24, 45, 75, 66]
3	Process digit exp=10 (tens place)	10	0: 802, 2 1: 2: 24 3: 4: 45 5: 6: 66 7: 170, 75 8: 9: 90	[802, 2, 24, 45, 66, 170, 75, 90]	[802, 2, 24, 45, 66, 170, 75, 90]
4	Process digit exp=100 (hundreds place)	100	0: 2, 24, 45, 66, 75, 90 1: 170 2: 3: 4: 5: 6: 7: 8: 802 9:	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]
5	Check next digit exp=1000	1000	-	-	Stop: max/exp=0, sorting complete

💡 When max/exp becomes 0 (1000), no more digits to process, sorting ends.

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]
exp	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 (units place)?

Because radix sort relies on stable sorting at each digit level, starting from the least significant digit ensures that the order of digits processed earlier is preserved, as shown in steps 2 and 3 where the array is reordered by units then tens digits.

What happens if numbers have different digit lengths?

Shorter numbers are treated as having leading zeros in higher digit places, so they go into bucket 0 for those digits, as seen in step 4 where numbers like 2 and 24 fall into bucket 0 for the hundreds place.

Why do we stop when max/exp becomes 0?

Because it means we have processed all digit places of the largest number, so no further sorting is needed, as indicated in step 5 where max/exp=0 stops the loop.

Visual Quiz - 3 Questions

Look at the execution table at Step 3, which bucket contains the number 170?

A Bucket 0

B Bucket 1

C Bucket 7

D Bucket 9

💡 Hint

Check the 'Buckets (0-9)' column at Step 3 for where 170 is placed.

At which step does the array first become sorted by the hundreds digit?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Current Digit (exp)' and 'Array After Collection' columns to see when hundreds place sorting happens.

If the maximum number was 99 instead of 802, how many steps would the sorting loop run?

A 1

B 2

C 3

D 4

💡 Hint

Check the 'exp' variable changes and when max/exp becomes 0 in the variable_tracker.

Concept Snapshot

Radix Sort Algorithm:
- Sorts numbers digit by digit from least to most significant
- Uses buckets (0-9) for each digit
- Collects numbers after each digit sorting
- Repeats until all digits processed
- Stable and efficient for fixed digit lengths

Full Transcript

Radix sort finds the largest number to know how many digits to process. It starts sorting from the least significant digit (units place), placing numbers into buckets based on that digit. Then it collects numbers back in order. This repeats for tens, hundreds, and so on until all digits are processed. The array becomes sorted after the last digit is handled. The process stops when the digit place exceeds the largest number's digits. This method works well because it sorts numbers by each digit without comparing whole numbers directly.