Radix Sort Visualizer

How it works

1. Find the largest key to know how many digits d it has (shift every key by −min first if there are negative numbers).
2. Start with exp = 1, the ones digit.
3. Distribute: for each element in order, compute its digit ⌊A[i] / exp⌋ mod 10 and append the element to the end of that bucket.
4. Collect: concatenate buckets 0 through 9 back into A, each in first-in, first-out order.
5. Multiply exp by 10 and repeat until every digit of the largest key has been used.

Worked example: sorting [170, 45, 75, 90, 802, 24, 2, 66]

The visualizer above opens on this classic example. The largest key, 802, has three digits, so there are three passes.

• Ones digit: bucket 0 gets 170, 90 · bucket 2: 802, 2 · bucket 4: 24 · bucket 5: 45, 75 · bucket 6: 66 → [170, 90, 802, 2, 24, 45, 75, 66].
• Tens digit: 0: 802, 2 · 2: 24 · 4: 45 · 6: 66 · 7: 170, 75 · 9: 90 → [802, 2, 24, 45, 66, 170, 75, 90].
• Hundreds digit: 0: 2, 24, 45, 66, 75, 90 · 1: 170 · 8: 802 → [2, 24, 45, 66, 75, 90, 170, 802].

Look at bucket 0 in the last pass: six numbers whose hundreds digit is 0 arrive already ordered by their last two digits, because the earlier passes sorted them and each pass keeps that order. The visualizer counts 48 moves: 8 elements × 3 passes × (one move into a bucket + one move back).

Why least-significant-digit first works

After pass p the array is sorted by its last p digits. The next pass sorts by digit p + 1, and when two numbers share that digit, a stable pass leaves them in the order the earlier passes established — sorted by their lower digits. By induction, after d passes the array is sorted by all d digits.

So every pass must be stable; with an unstable pass the earlier work would be scrambled. MSD (most significant digit first) radix sort works the other way round: it splits by the top digit and recursively sorts each bucket, which suits variable-length keys such as strings.

Time complexity: O(d·(n + b))

Each pass moves every element into a bucket and back and walks b = 10 buckets, so one pass is O(n + b). With d passes the total is O(d·(n + b)) in every case — the order of the input doesn't matter.

Is that faster than O(n log n)? When d is a small constant, yes: sorting a million 32-bit integers one byte at a time (base 256) takes 4 passes, while a comparison sort needs around 20 million comparisons. But d grows with the key size — n distinct keys need at least log_b n digits — so radix sort wins when keys are short compared with the number of elements, not always.

Radix sort vs counting sort and comparison sorts

• Counting sort needs a counter for every possible value (O(k) memory). Radix sort runs a counting-style pass on one digit at a time, so it handles huge ranges with only b buckets.
• Quick sort and merge sort work on any keys that can be compared; radix sort needs keys that split into digits — integers, fixed-length strings, dates, IP addresses.
• Production implementations usually use base 256 (one byte per pass) and a counting-sort pass instead of bucket lists, which is faster and avoids allocating lists.
• Radix sort is stable and needs O(n + b) extra memory, so the simple version shown here is not in-place.

Common mistakes and interview tips

• Starting this algorithm from the most significant digit. LSD must start with the ones digit; MSD needs a recursive sort per bucket.
• Using an unstable pass for a digit, for example pushing elements to the front of a bucket.
• Stopping too early: the number of passes comes from the largest key's digit count, not from the first element.
• Negative numbers: shift every key by −min first (as the code here does) or sort negatives separately; plain digit extraction breaks on them.
• Interview angle: “sort n integers in the range 0 … n³ − 1 in linear time.” Radix sort in base n needs just 3 passes of O(n) each.

Time and space complexity

Radix Sort in Python

def radix_sort_lsd(A):
    # LSD radix sort (base 10) of integers, in place. Stable.
    # O(d * (n + 10)) time for d digits, O(n) extra space.
    # Negative numbers: every key is shifted by off = -min(A) first.
    n = len(A)
    if n == 0:
        return
    off = max(0, -min(A))               # keys must be >= 0
    max_key = max(A) + off
    exp = 1
    while exp <= max_key:               # one pass per digit
        bucket = [[] for _ in range(10)]    # 10 empty queues
        for i in range(n):
            d = (A[i] + off) // exp % 10
            bucket[d].append(A[i])      # append to the END: stable
        # A <- bucket[0] ++ bucket[1] ++ ... ++ bucket[9]
        A[:] = [x for b in bucket for x in b]
        exp *= 10

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Counting Sort VisualizerCounting sort sorts integers in O(n + k) time by counting each value and placing elements with prefix sums, with no comparisons. Watch every phase animated.
• Merge Sort VisualizerMerge sort splits the array in half, sorts each half recursively and merges the sorted halves, in O(n log n) time. Watch every split and merge animated.
• Quick Sort VisualizerQuick sort picks a pivot, moves smaller values left and larger ones right, then recurses: O(n log n) on average. Watch Lomuto and Hoare partitioning animated.
• Sorting Algorithm VisualizerSorting algorithm visualizer: watch bubble, selection, insertion, shell, counting, radix, merge and quick sort step by step, then race them in Compare mode.