Radix Sort

DSA · Sorting Algorithms

Theory

Radix sort sorts integers digit by digit, from the least significant digit to the most significant, using a stable sort (usually counting or bucket sort) for each digit. After processing every digit position the numbers are fully sorted. Its time is O(d × (n + b)), where d is the number of digits and b the base (10 for decimal).

Why we use it

It sorts large lists of fixed-length integers or strings in linear time with respect to n.

When to use it

Use it for phone numbers, IDs, dates as integers, or fixed-length strings, when d is small.

How it works

  1. Find the maximum number of digits d
  2. Start with the least significant digit
  3. Stable-sort all numbers by this digit (counting sort)
  4. More digits left? Yes: Move to the next digit, repeat. No: Array is sorted.
  5. Done

Syntax

for each digit position (ones, tens, hundreds...):
    distribute numbers into buckets 0-9 by that digit
    collect buckets in order

Time: O(d·(n+b))   Space: O(n+b)   Stable

Example

def radix_sort(arr):
    exp = 1
    while max(arr) // exp > 0:
        buckets = [[] for _ in range(10)]
        for num in arr:
            buckets[(num // exp) % 10].append(num)
        arr = [n for b in buckets for n in b]
        print("After digit", exp, ":", arr)
        exp *= 10
    return arr

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

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic