• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Radix Sort

← Previous Next →

Radix sort is a powerful non-comparison sorting algorithm that sorts numbers digit by digit. Instead of comparing elements directly, it groups numbers based on each digit starting from the least significant digit (LSD) or the most significant digit (MSD). Radix sort becomes extremely efficient when dealing with large lists of integers that have a similar number of digits.

In this tutorial, you’ll learn how radix sort works, the difference between LSD and MSD methods, how counting sort is used inside radix sort, how to implement the algorithm in Python and where it is used in real-world systems. Understanding radix sort helps you move toward advanced sorting logic and improves your mental model for data processing.

What Is Radix Sort?

Radix sort is a digit-based sorting algorithm that processes numbers one digit at a time. It usually uses counting sort as a helper algorithm to sort the digits at each position.

The core idea is simple:

  • Sort numbers by 1s digit

  • Then sort by 10s digit

  • Then sort by 100s digit

  • Continue until the largest digit place is processed

After going through all digit places, the list becomes completely sorted.

How Radix Sort Works Step by Step

Let’s use this list:

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

Step 1: Sort by 1s place

Result after sorting by unit digit:

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

Step 2: Sort by 10s place

Using the above result:

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

Step 3: Sort by 100s place

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

After all digit places are processed, the list becomes completely sorted.

Why Use Radix Sort?

Radix sort offers some strong benefits:

  • Runs in linear time O(nk)

  • Works extremely well for numbers with equal digit lengths

  • No element-to-element comparisons

  • Stable sorting

  • Faster than comparison-based sorts for certain datasets

Because of its efficiency, radix sort is widely used in areas where speed matters and input values follow a predictable structure.

Radix Sort Algorithm in Python

Radix sort uses counting sort internally. Here is the complete implementation:

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

    for num in data:
        index = (num // exp) % 10
        count[index] += 1

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

    for i in range(n - 1, -1, -1):
        index = (data[i] // exp) % 10
        output[count[index] - 1] = data[i]
        count[index] -= 1

    return output


def radix_sort(data):
    if not data:
        return data

    max_val = max(data)
    exp = 1

    while max_val // exp > 0:
        data = counting_sort_exp(data, exp)
        exp *= 10

    return data

This version processes digits from lowest place to highest place.

Example Usage

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

Output:

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

This shows how each digit pass gradually organizes the list.

Time Complexity of Radix Sort

Radix sort’s time depends on:

  • n = number of elements

  • k = number of digits in the largest number

The complexity is:

  • Best case: O(nk)

  • Average case: O(nk)

  • Worst case: O(nk)

This performance can outperform comparison sort which cannot go below O(n log n).

When Radix Sort Works Best

Use radix sort when:

  • Sorting integers

  • Numbers share a similar number of digits

  • Values have fixed length (like IDs, phone numbers, roll numbers)

  • You want stable and predictable performance

  • You need high speed for large datasets

This makes radix sort a good choice for large structured numeric data.

When Radix Sort Is Not Suitable

Avoid radix sort when:

  • Values have very large digit lengths

  • Data cannot easily break into digits

  • Memory for counting arrays is limited

  • Comparison-based sorting is more practical

For datasets with huge ranges or mixed data types, quick sort or merge sort works better.

Real-Life Uses of Radix Sort

Radix sort appears in many systems where large numeric datasets are sorted frequently:

Database indexing

Indexes sorted by numeric keys use digit-wise logic.

Processing phone numbers

Fixed-length digits make sorting straightforward.

Sorting long user IDs

Web platforms often store large structured IDs.

Postal code sorting

Postal systems often use digit-based sorting.

Used inside radix tree and trie structures

These structures use digit or character ordering internally.

Step-by-Step Example

List:

[121, 432, 564, 23, 1, 45, 788]

Step 1: Sort by 1s place
Step 2: Sort by 10s place
Step 3: Sort by 100s place

Final sorted output:

[1, 23, 45, 121, 432, 564, 788]

Radix sort repeats counting sort on digit positions until the largest one is covered.

Practical Examples

Example 1: Sort numbers

print(radix_sort([432, 8, 530, 90, 88]))

Example 2: Sort roll numbers

rolls = [112, 59, 203, 8, 15]
print(radix_sort(rolls))

Example 3: Sort random IDs

ids = [5012, 4021, 8999, 1020]
print(radix_sort(ids))

Example 4: Sort small list

print(radix_sort([3, 1, 2]))

Example 5: Sort duplicate values

print(radix_sort([22, 11, 22, 33]))

Example 6: Sort odd and even values

print(radix_sort([19, 2, 45, 11, 9]))

Example 7: Sort fixed-length data

data = [100, 999, 120, 450]
print(radix_sort(data))

Example 8: Sort values with zero

print(radix_sort([0, 10, 5, 100]))

Example 9: Sort increasing values

print(radix_sort([1, 2, 3, 4, 5]))

Example 10: Sort decreasing values

print(radix_sort([9, 8, 7, 6, 5]))

Summary of the Tutorial

Radix sort works by sorting numbers digit by digit using counting sort as a helper algorithm. You learned how the algorithm processes each digit place, why it becomes fast for large datasets with fixed digit lengths and where it is commonly used in real-world applications. Radix sort is a key algorithm for dealing with structured numeric data efficiently.

Practice Questions

Q1. Write a Python program to sort the list [34, 2, 122, 98, 1] using radix sort.

Q2. Write a Python program to modify radix sort to print the array after each digit pass.

Q3. Write a Python program to generate a random list of 20 integers and sort it using radix sort.

Q4. Write a Python program to count and display the total number of digit passes required in radix sort.

Q5. Write a Python program to accept a list of integers from user input and sort it using radix sort.

Q6. Write a Python program to test radix sort on numbers up to 100000 and display the sorted output.

Q7. Write a Python program to add a check for an empty list before performing radix sort.

Q8. Write a Python program to modify radix sort to work using base-16 (hexadecimal digits).

Q9. Write a Python program to compare the output of radix sort with the built-in sorted() function.

Q10. Write a Python program to implement radix sort by treating numbers as strings of digits.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top