Sorting Tested code in 3 languages

Radix Sort, Visualized One Digit at a Time

Sort by the ones digit, then the tens, then the hundreds, each time with a stable counting sort. After the last digit the array is sorted, and no two values were ever compared to decide their order. Press play to watch each digit pass next to the exact line of code that runs.

Crio.Do · Last updated 19 November 2026

Interactive radix sort

The largest value is 802. It has 3 digits, so sort 3 times: by the ones, then the tens, then the hundreds. Shorter numbers count as having leading zeros.

0Counter updates
0Writes
1/–Step
def radix_sort(a):    if not a:        return    low = min(a)    if low < 0:  # digits need values >= 0: shift up        for i in range(len(a)):            a[i] -= low    big = max(a)    exp = 1    while big // exp > 0:        sort_by_digit(a, exp)        exp *= 10    if low < 0:        for i in range(len(a)):            a[i] += low  def sort_by_digit(a, exp):    count = [0] * 10    for v in a:        count[v // exp % 10] += 1    for d in range(1, 10):        count[d] += count[d - 1]    out = [0] * len(a)    for i in range(len(a) - 1, -1, -1):        d = a[i] // exp % 10        count[d] -= 1        out[count[d]] = a[i]    for i in range(len(a)):        a[i] = out[i]

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How radix sort works

Radix sort sorts numbers the way a post office sorts letters by PIN code: one digit at a time. The surprise is the order. LSD (least significant digit) radix sort starts with the last digit, the ones, then the tens, then the hundreds. Each pass puts the values into 10 groups, 0 to 9, by that digit alone.

Why does starting from the wrong end work? Because every pass is stable: values with the same digit keep the order the previous pass gave them. After the ones pass the array is sorted by its last digit. The tens pass groups by the tens digit, and inside each group the ones order survives, so the array is now sorted by its last two digits. After the hundreds pass it is sorted by all three. In the visualizer's array, 170 and 75 both have tens digit 7; the ones pass already put 170 (ones digit 0) ahead of 75 (ones digit 5), and the tens pass keeps them that way.

Each digit pass is a counting sort with 10 counters: count how many values have each digit, take running totals, then walk the array from the right and place every value. Short numbers count as having leading zeros, which is why 2 and 45 land in the 0 group of the hundreds pass.

The number of passes is the number of digits d of the largest value, so the cost is O(d · (n + 10)). For numbers with a fixed number of digits that is linear in n. Digits do not have to be decimal: real implementations usually take 8 bits at a time, so any 32-bit integer needs exactly 4 passes with 256 counters each.

The algorithm in 5 steps

  1. 1 Find the largest value; its number of digits is the number of passes.
  2. 2 Start with exp = 1, the ones digit. The digit of v is v // exp % 10.
  3. 3 Run a stable counting sort on that digit: count, take running totals, place values from right to left into out, copy back.
  4. 4 Multiply exp by 10 and repeat for the tens, hundreds... until exp is bigger than the largest value.
  5. 5 Negative values: shift everything up by −min before sorting and back down after, as the code here does.

Worked example

These are the seven 3-digit numbers from Figure 8.3 of CLRS (Introduction to Algorithms), run through the same code as the visualizer. Each row is the array after one digit pass: ones, then tens, then hundreds. The counting and placing steps inside each pass are counted in the total but not listed.

Input: [329, 457, 657, 839, 436, 720, 355]

  1. Step 40 After the ones pass: 720, 355, 436, 457, 657, 329, 839. The values are now in order of their last digit, and values with the same digit kept their input order. 720355436457657329839
  2. Step 79 After the tens pass: 720, 329, 436, 839, 355, 457, 657. The values are now in order of their last 2 digits, and values with the same digit kept their order from the pass before. 720329436839355457657
  3. Step 118 After the hundreds pass: 329, 355, 436, 457, 657, 720, 839. That was the last digit, so the array is sorted. 329355436457657720839

Total for this run: 3 digit passes, 69 counter updates and 42 writes, in 119 animation steps. Result: 329, 355, 436, 457, 657, 720, 839.

Time and space complexity

Best

O(d · (n + k))

Every pass runs in full whatever the input order. d is the number of digits of the largest value and k the number of possible digits, 10 here.

Average

O(d · (n + k))

The same d passes. With d and k fixed, for example 32-bit integers in 4 byte passes of 256 counters, that is O(n).

Worst

O(d · (n + k))

One huge value makes d large for everyone: [1, 2, 3, 1000000000] needs 10 decimal passes to sort four numbers.

Space

O(n + k)

An output array of n values and k counters, reused on every pass. Not in place.

Stable:
Yes
In place:
No
Comparison sort:
No
Works on:
Integers and fixed-length keys

Same 8 numbers, comparison sorts vs radix sort

Every comparison sort needs at least ⌈log₂(n!)⌉ comparisons in the worst case, 16 for 8 values, and that grows like n log n. Radix sort never compares two values to order them: on the visualizer's numbers it runs 3 digit passes, with 75 counter updates and 48 writes. Computed from the code on these pages, not typed in.

AlgorithmComparisonsOther work
Radix sort0 (after finding the largest value)75 counter updates, 48 writes
Merge sort1724 writes
Quick sort398 swaps
Heap sort2618 swaps
Insertion sort2116 shifts

Fewer operations on 8 numbers is not the point; the growth is. Comparison sorts grow like n log n. Radix sort grows like d · (n + 10), where d is the number of digits in the largest value.

When to use it, and when not to

Good fit

  • Large numbers of integers with a bounded size: IDs, timestamps, 32- or 64-bit keys. With byte-sized digits a 32-bit key needs 4 passes, whatever n is, so for millions of keys it can beat O(n log n) sorts.
  • Fixed-length keys made of characters or digits: dates as YYYYMMDD, PIN codes, phone numbers, equal-length strings. LSD radix sort on each character position sorts them in d passes.
  • You need a stable sort by a composite key: sort by the minor key first, then by the major key with a stable sort. That is the LSD idea, and it is how punched-card sorting machines were operated, one column per run.
  • As a building block: suffix-array construction and other string algorithms use radix sort on integer ranks to get linear-time passes.

Pick something else when

  • Few values or values of very different lengths. One huge number forces extra passes for everyone, and for small n a comparison sort is simpler and as fast.
  • Keys that are not integers or fixed-length strings, such as floats compared with a tolerance or objects sorted by a custom rule. (IEEE floats can be radix sorted after a bit trick, but that is beyond a first implementation.)
  • Memory is tight: radix sort needs an n-sized output array. Heap sort works in place.
  • You just need to sort in application code. Your language's built-in sort is tuned, tested and usually fast enough; reach for radix sort when profiling says sorting integer keys is the bottleneck.

Common mistakes and bugs

  1. 1.Using an unstable sort for each digit

    LSD radix sort is only correct if each pass is stable. Take [25, 21]: the ones pass gives [21, 25]. In the tens pass both have digit 2, and an unstable pass is free to output [25, 21], which is wrong. Counting sort placed right to left, as here, is stable.

  2. 2.Starting from the most significant digit with the same loop

    Running the passes hundreds, then tens, then ones lets the last pass (the ones) undo the earlier ones: [21, 15] sorted by tens gives [15, 21], then by ones gives [21, 15]. MSD radix sort exists, but it must recurse into each digit group separately instead of re-sorting the whole array.

  3. 3.Feeding it negative numbers as they are

    In Java, -5 % 10 is −5, so count[-5] throws an exception. In Python, -5 // 1 % 10 is 5, so −5 is quietly sorted as if it were 5. Shift all values up by −min first and back after, as the code here does, or sort negatives and positives separately.

  4. 4.Letting exp overflow in Java

    With int exp, the pass after 10⁹ computes 10¹⁰, which overflows to 1,410,065,408. For a largest value above that, the loop runs an extra pass on a meaningless "digit" and can scramble a sorted array. The Java code here declares exp as long.

  5. 5.Recomputing the digit with floating point

    Writing the digit as Math.floor(v / Math.pow(10, p)) % 10 or with log10 to count digits invites rounding errors on large values. Keep exp as an exact integer that is multiplied by 10 each pass, and get the number of passes from the loop condition, not from a logarithm.

Interview questions

Try answering before you open the model answer.

Q1 Why does LSD radix sort work when it starts from the least significant digit?

Model answer: Each pass is stable. By induction, after pass p the array is sorted by its last p digits: the new pass orders by digit p, and values with an equal digit p keep the order of the previous pass, which was by the last p − 1 digits. After the last digit the array is sorted by the whole number.

Q2 What is the time complexity of radix sort, and when is it better than O(n log n)?

Model answer: O(d · (n + k)) for n values with d digits of k possible values each (CLRS, Lemma 8.3). It is better when d is small and fixed: 32-bit integers take 4 passes with k = 256, which is linear in n. If d grows with n, for example distinct values need about log n digits, the advantage over a good comparison sort shrinks.

Q3 Sort n integers in the range 0 to n² − 1 in O(n) time.

Model answer: Write each number in base n: it has at most two digits, v // n and v % n. Two passes of radix sort, each a counting sort with k = n counters, take O(n) each. Counting sort alone would need n² counters, and comparison sorts need O(n log n).

Q4 What is the difference between LSD and MSD radix sort?

Model answer: LSD processes digits from the right, always re-sorting the whole array with a stable pass, which is simple and iterative but requires keys of equal length (or padding). MSD starts from the left, splits the values into groups by that digit and recurses into each group, so it can stop early, handles variable-length strings naturally and resembles a trie traversal.

Q5 Why is counting sort used inside radix sort and not, say, quick sort?

Model answer: Two reasons. The digit has only 10 (or 256) possible values, which is exactly where counting sort is O(n + k), linear per pass. And it is stable, which LSD radix sort needs for correctness. Quick sort is neither linear nor stable, so the passes would cost O(n log n) each and could give a wrong result.

Frequently asked questions

What is the time complexity of radix sort?

O(d · (n + k)): n values, d digits in the largest value, k possible digit values (10 for decimal). Every pass runs in full, so best and worst case are the same. With fixed-size keys, such as 32-bit integers sorted a byte at a time, that is linear time.

Is radix sort stable?

Yes, LSD radix sort is stable, and it has to be built from a stable digit sort to work at all. Each pass here is a counting sort that places values from right to left, so values with the same digit keep their order. That is also why equal values in the whole array keep their original order.

Is radix sort faster than quick sort?

Sometimes. For millions of integer keys of fixed size, radix sort does a few linear passes and no comparisons, and can win. For small arrays, mixed key lengths or general objects, a tuned comparison sort such as quick sort or Timsort is usually faster and needs no extra memory, which is why built-in sorts are comparison sorts.

Can radix sort handle negative numbers?

Not directly, because the digits of a negative number are not defined the same way, and the % operator behaves differently in Python and Java. The usual fix, used in the code on this page, is to subtract the minimum from every value, sort, then add it back. The visualizer itself draws digits of values 0 to 999.

Why does radix sort start from the least significant digit?

Because each later pass is stable, it keeps the order of the earlier passes for values with the same digit. Sorting by the ones, then tens, then hundreds leaves the hundreds digit, the most important one, decided last, with ties already ordered by the lower digits. Starting from the most significant digit needs recursion into groups instead.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Section 8.3, Radix sort: LSD with a stable digit sort, Lemma 8.3, Θ(d(n + k)), and Figure 8.3, the seven numbers in the worked example.
  2. Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., Addison-Wesley, 1998)
    Section 5.2.5, Sorting by distribution: radix sorting and its history on punched-card machines.
  3. Wikipedia, "Radix sort"
    History: Herman Hollerith's tabulating machines (1887), punched-card sorting in common use by 1923, and the first memory-efficient computer version by Harold H. Seward at MIT in 1954. The visualizer uses its LSD example array.

The animation, the worked example and the step counts are all generated by one implementation of radix sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms