Python Program for Radix Sort with Example and Explanation

A Python program for radix sort uses digit-by-digit sorting starting from the least significant digit using counting sort repeatedly; for example, def radix_sort(arr): ... sorts the list arr by processing each digit place.

Examples

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

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

Input[5, 3, 8, 6, 2]

Output[2, 3, 5, 6, 8]

Input[]

Output[]

How to Think About It

To sort numbers using radix sort, think of sorting them by each digit starting from the rightmost digit to the leftmost. We repeatedly group numbers by their current digit using a stable sorting method like counting sort, so after processing all digits, the list becomes fully sorted.

Algorithm

1

Find the maximum number to know the number of digits.

2

Start with the least significant digit (rightmost).

3

Use counting sort to sort the array based on the current digit.

4

Move to the next more significant digit (left).

5

Repeat counting sort for each digit until all digits are processed.

6

Return the sorted array.

Code

python

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]


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


arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)

Output

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

Dry Run

Let's trace the list [170, 45, 75, 90, 802, 24, 2, 66] through the radix sort code.

1

Find max and start with exp=1

max_num = 802, exp = 1 (units place)

2

Counting sort by units digit

Sort by last digit: [170(0), 90(0), 802(2), 2(2), 24(4), 45(5), 75(5), 66(6)] -> [170, 90, 802, 2, 24, 45, 75, 66]

3

Counting sort by tens digit (exp=10)

Sort by tens digit: [802(0), 2(0), 24(2), 45(4), 66(6), 170(7), 75(7), 90(9)] -> [802, 2, 24, 45, 66, 170, 75, 90]

4

Counting sort by hundreds digit (exp=100)

Sort by hundreds digit: [2(0), 24(0), 45(0), 66(0), 75(0), 90(0), 170(1), 802(8)] -> [2, 24, 45, 66, 75, 90, 170, 802]

5

No more digits, sorting complete

Final sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

Step	Array State
Initial	[170, 45, 75, 90, 802, 24, 2, 66]
After exp=1	[170, 90, 802, 2, 24, 45, 75, 66]
After exp=10	[802, 2, 24, 45, 66, 170, 75, 90]
After exp=100	[2, 24, 45, 66, 75, 90, 170, 802]

Why This Works

Step 1: Sorting by each digit

Radix sort works by sorting numbers digit by digit starting from the least significant digit using counting sort, which is stable and keeps the order of equal elements.

Step 2: Using counting sort for stability

Counting sort groups numbers by the current digit without changing the relative order of numbers with the same digit, preserving previous sorting steps.

Step 3: Repeating for all digit places

By repeating counting sort for each digit place (units, tens, hundreds, etc.), the array becomes fully sorted after the last digit is processed.

Alternative Approaches

LSD Radix Sort with Buckets

python

def radix_sort_buckets(arr):
    max_num = max(arr) if arr else 0
    exp = 1
    while max_num // exp > 0:
        buckets = [[] for _ in range(10)]
        for num in arr:
            buckets[(num // exp) % 10].append(num)
        arr = [num for bucket in buckets for num in bucket]
        exp *= 10
    return arr

arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort_buckets(arr)
print(sorted_arr)

Uses lists as buckets instead of counting arrays; easier to understand but uses more memory.

Recursive Radix Sort

python

def radix_sort_recursive(arr, exp=1):
    if len(arr) <= 1 or exp > max(arr, default=0):
        return arr
    buckets = [[] for _ in range(10)]
    for num in arr:
        buckets[(num // exp) % 10].append(num)
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(radix_sort_recursive(bucket, exp * 10))
    return sorted_arr

arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort_recursive(arr)
print(sorted_arr)

Uses recursion to sort by each digit; elegant but may have overhead for large lists.

Complexity: O(d * (n + k)) time, O(n + k) space

Time Complexity

Radix sort runs in O(d * (n + k)) where n is number of elements, d is number of digits, and k is digit range (10 for decimal). Each digit requires a counting sort pass.

Space Complexity

Extra space is needed for counting arrays and output arrays, making space complexity O(n + k). It is not fully in-place.

Which Approach is Fastest?

Counting sort based radix is faster and uses less memory than bucket-based versions, but bucket versions are easier to understand.

Approach	Time	Space	Best For
Counting Sort Radix	O(d*(n+k))	O(n+k)	Large numeric arrays with fixed digit range
Bucket Radix Sort	O(d*n)	O(n)	Easier to implement, more memory use
Recursive Radix Sort	O(d*n)	O(n)	Elegant code, smaller inputs