Radix Sort Explained

Radix Sort Algorithm

The Radix Sort algorithm sorts an array by individual digits, starting with the least significant digit (the rightmost one).

What Radix Sort Is

Radix sort sorts numbers digit by digit, starting from the least significant digit (units place), then tens, hundreds, etc.

It does NOT compare numbers directly like bubble sort or quick sort.

Key Mathematical Idea

Extracting a digit

This line is the heart of radix sort:

radixIndex = (val // exp) % 10

exp is a place-value divisor

Breakdown (pure math):

Expression	Meaning
val // exp	Shifts digits to the right
% 10	Extracts the last digit

Example: val = 170

Units place (exp = 1)

170 // 1 = 170
170 % 10 = 0   → units digit

Tens place (exp = 10)

170 // 10 = 17
17 % 10 = 7   → tens digit

Hundreds place (exp = 100)

170 // 100 = 1
1 % 10 = 1   → hundreds digit

This is the only math radix sort uses

Why radixArray has 10 buckets

radixArray = [[], [], [], [], [], [], [], [], [], []]

Because digits range from 0 to 9.

Each bucket represents:

bucket[0] → digit 0
bucket[1] → digit 1
...
bucket[9] → digit 9

Step-by-step Execution

Original list

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

Pass 1: Units digit (exp = 1)

Number	Units digit	Bucket
170	0	bucket[0]
45	5	bucket[5]
75	5	bucket[5]
90	0	bucket[0]
802	2	bucket[2]
24	4	bucket[4]
2	2	bucket[2]
66	6	bucket[6]

Buckets become:

0: [170, 90]
2: [802, 2]
4: [24]
5: [45, 75]
6: [66]

Rebuild list:

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

Pass 2: Tens digit (exp = 10)

Number	Tens digit
170	7
90	9
802	0
2	0
24	2
45	4
75	7
66	6

Rebuilt list:

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

Pass 3: Hundreds digit (exp = 100)

Number	Hundreds digit
802	8
2	0
24	0
45	0
66	0
170	1
75	0
90	0

Rebuilt list:

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

Final Sorted Output

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

Why It Works (Simple Logic)

• Lower digits are sorted first
• Higher digits refine the order
• Stability is preserved (relative order remains correct)

Mathematically:

Number = (hundreds × 100) + (tens × 10) + units

Sorting digit-by-digit reconstructs the full number order.

Radix sort = repeated digit extraction using

(number // place) % 10

Python Code

mylist = [170, 45, 75, 90, 802, 24, 2, 66]
print("Original array:", mylist)
radixArray = [[], [], [], [], [], [], [], [], [], []]
maxVal = max(mylist)
exp = 1

while maxVal // exp > 0:
    while len(mylist) > 0:
        val = mylist.pop()
        radixIndex = (val // exp) % 10
        radixArray[radixIndex].append(val)

    for bucket in radixArray:
        while len(bucket) > 0:
            val = bucket.pop()
            mylist.append(val)

    exp *= 10

print(mylist)

Further Reading

1. ...