Lesson menuPython TutorialHideShow

Python Tutorial

Radix Sort

Sort integers digit by digit, from least to most significant, using a stable counting sort per digit.

← Counting SortMerge Sort →

Sorting by Digits

Radix sort avoids element comparisons entirely. It processes numbers one digit at a time — least-significant-digit (LSD) first — using a stable sort (usually counting sort) at each digit. After processing every digit, the array is fully sorted. For n numbers with d digits it runs in O(d · (n + b)), where b is the base (10 for decimal).

Implementation (LSD, base 10)

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    counts = [0] * 10                # digits 0-9

    for x in arr:
        digit = (x // exp) % 10
        counts[digit] += 1

    for i in range(1, 10):           # prefix sums
        counts[i] += counts[i - 1]

    for x in reversed(arr):          # right-to-left keeps it STABLE
        digit = (x // exp) % 10
        counts[digit] -= 1
        output[counts[digit]] = x
    return output

def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:         # one pass per digit
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

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

Why Stability Is Essential

Radix sort only works if each digit pass preserves the order established by previous, less-significant digits. That is exactly what a stable sort guarantees. Using an unstable sort per digit would scramble the partial ordering and produce wrong results.

Trace 170 and 90: after the units pass both end in 0 and keep their order; the tens and hundreds passes then place them correctly. Stability carries the earlier work forward.

Complexity

MetricValue
TimeO(d · (n + b))
SpaceO(n + b)
Stable?Yes
ComparisonsNone

When the number of digits d is small and fixed, radix sort is effectively O(n) — faster than comparison sorts on large sets of bounded-size integers.

Limitations

  • Designed for integers or fixed-length strings, not arbitrary comparables.
  • Negative numbers need special handling (sort magnitudes and reverse, or offset by the minimum).
  • Very large numbers (many digits) increase d and erode the advantage.

Best Practices

  • Use radix sort for large volumes of integers or fixed-width keys.
  • Always pair it with a stable per-digit sort (counting sort).
  • Consider a larger base (e.g. 256) to reduce the number of passes on big data.
  • For general data, comparison sorts remain the practical default.

Try It Yourself

Exercise 1: Why must the per-digit sort in radix sort be stable?

Show solution

Stability preserves the ordering established by earlier (less-significant) digit passes; an unstable sort would scramble that partial order and produce wrong results.

Exercise 2: How many digit passes does radix sort make on the number 802?

Show solution

Three — one for the units, tens, and hundreds digits.

📘 Real-World Deep Dive

Knowing <strong>DSA Radix Sort (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.

Real-Life Scenario

An end-to-end usage of DSA Radix Sort that you'd actually see in a data pipeline or analytics notebook.

Real-Life Example

def radix(xs):
    if not xs: return xs
    iters = max(len(str(abs(x))) for x in xs)
    place = 1
    for _ in range(iters):
        buckets = [[] for _ in range(10)]
        for x in xs:
            buckets[(x // place) % 10].append(x)
        xs = [v for b in buckets for v in b]
        place *= 10
    return xs

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

Expected Output

(see source)

Common mistakes

  • Off-by-one errors in binary-search: the standard idiom is while lo <= hi with mid = (lo + hi) // 2.
  • Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
  • Comparison algorithms (sorted(iterable)) are stable by default in Python — surprising for Java/C++ users.
  • Treating DSA Radix Sort as a black box without reading the docs — the API has subtle defaults that bite when you scale.

🚀 Performance & Best Practices

  • Use bisect.bisect_left / bisect_right instead of writing your own binary search.
  • Convert a sorted search into a tuple-access pattern with numpy.searchsorted for huge arrays.
  • Use heapq for priority queues instead of maintaining a sorted list manually.
  • When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.

🧪 Try It Yourself

  1. Reproduce the snippet on a representative slice of your own data.
  2. Profile the snippet with cProfile or timeit and find the single biggest improvement.
  3. Generalise the snippet into a small, reusable function you can drop into future projects.

FAQ: Radix Sort

Common questions about this page.

What is Radix Sort?

Radix Sort is a DSA lesson that explains radix sort in Python. Sort integers digit by digit, from least to most significant, using a stable counting sort per digit. Copy the samples and run them in the Python editor. It is written for beginners who want a clear definition and working examples.

Should I run radix sort examples locally for better learning?

Yes. Use the browser editor on StudyGrid for a quick check, then Download the example and run it on your computer. Local runs show real errors and the real toolchain, which is one of the fastest ways to learn radix sort in this DSA Python lesson (Radix Sort).

How do I use radix sort in Python?

To use radix sort in Python, follow the examples on this StudyGrid page. Copy a snippet, run it in the browser, then Download and run it locally for better learning. Change the values and compare the output.

What is the syntax of radix sort?

This Radix Sort tutorial shows radix sort syntax with short Python examples. Use the code blocks in this lesson for the exact statements, then try them in your editor.

Radix Sort example for beginners

Yes. This page includes a beginner radix sort example you can copy and run. It is designed for searches such as "radix sort for beginners", "radix sort example", and "how to use radix sort".

What are common mistakes with radix sort?

Common radix sort mistakes include wrong syntax, mixing types, and skipping practice. Work through this DSA chapter in order, run every example, and check the output before moving on.

Why should I learn radix sort?

Radix Sort is used in real Python work. Learning radix sort helps you write clearer programs and continue the DSA tutorial on StudyGrid.

Is Radix Sort free to learn online?

Yes. You can learn radix sort free on StudyGrid (studygrid.in). This chapter is part of the DSA path and includes examples, syntax, and next-step links.