Radix Sort Visualizer: Step-by-Step Animation & Complexity

Radix Sort

Category: Sorting | Time: O(d * (n+k)) | Space: O(n + k)

Input Data

Visualization

Visual representation of the data structure

About Radix Sort

A non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function radixSort(arr) {
    const max = Math.max(...arr);
    for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
        countingSort(arr, exp);
    }
    return arr;
}

function countingSort(arr, exp) {
    let n = arr.length;
    let output = new Array(n);
    let count = new Array(10).fill(0);
    for (let i = 0; i < n; i++) {
        count[Math.floor(arr[i] / exp) % 10]++;
    }
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (let i = n - 1; i >= 0; i--) {
        output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i];
        count[Math.floor(arr[i] / exp) % 10]--;
    }
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

Variable State

{
  "arr": "[170,45,75,90,802,24,2,66]",
  "max": 802
}

Radix Sort: How It Works

Last updated October 28, 2026

Overview

Radix Sort sorts integers one digit at a time, starting from the least significant digit (LSD). Each pass is a stable Counting Sort on a single digit, so after the pass for the tens digit, numbers with equal tens digits are still ordered by their units digit from the previous pass.

The number of passes equals the number of digits in the largest value. The loop variable exp is 1, 10, 100 and so on, and Math.floor(arr[i] / exp) % 10 extracts the current digit.

With the default input 170, 45, 75, 90, 802, 24, 2, 66, the maximum is 802, so there are three passes. After the units pass the order is 170, 90, 802, 2, 24, 45, 75, 66; after the tens pass it is 802, 2, 24, 45, 66, 170, 75, 90; the hundreds pass finishes the job.

Step by step

Find the maximum value to know how many digits to process.
For exp = 1, 10, 100, ... while max / exp >= 1:
Count how many numbers have each digit 0–9 at position exp.
Turn the counts into prefix sums and place numbers into output from right to left (for stability).
Copy output back and move to the next digit.

Complexity

Case	Cost	Why
Best case	O(d · (n + b))	d digits, n elements, base b = 10 buckets per pass.
Average case	O(d · (n + b))	Input order does not matter.
Worst case	O(d · (n + b))	Effectively linear when d is small and fixed.
Extra space	O(n + b)	Output array plus the 10-slot count array.

When to use it

Large arrays of fixed-width integers, IDs, IP addresses or dates.
Strings of equal length (sort character by character from the right).
When the key length d is small compared with log n.

Common mistakes

The implementation shown assumes non-negative integers; negatives need to be offset or sorted separately.
Using an unstable per-digit sort breaks the algorithm — later passes would scramble earlier ones.
A single very large value increases d, and with it the number of passes, for the whole array.

Worked Example: Radix Sort Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Radix Sort: follow each row, predict the next one, and compare. The run below takes 233 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input: 170, 45, 75, 90, 802, 24, 2, 66
Result: return value = [2, 24, 45, 66, 75, 90, 170, 802]

Step	Line	Array	What happens
1	2	[170, 45, 75, 90, 802, 24, 2, 66]	max = 802
63	23	[170, 90, 802, 2, 24, 45, 75, 66]	i = 0
64	22	[170, 45, 75, 90, 802, 24, 2, 66]	i = 1
65	23	[170, 90, 802, 2, 24, 45, 75, 66]	i = 1
66	22	[170, 90, 75, 90, 802, 24, 2, 66]	i = 2
67	23	[170, 90, 802, 2, 24, 45, 75, 66]	i = 2
68	22	[170, 90, 802, 90, 802, 24, 2, 66]	i = 3
69	23	[170, 90, 802, 2, 24, 45, 75, 66]	i = 3
70	22	[170, 90, 802, 2, 802, 24, 2, 66]	i = 4
71	23	[170, 90, 802, 2, 24, 45, 75, 66]	i = 4
72	22	[170, 90, 802, 2, 24, 24, 2, 66]	i = 5
73	23	[170, 90, 802, 2, 24, 45, 75, 66]	i = 5
74	22	[170, 90, 802, 2, 24, 45, 2, 66]	i = 6
75	23	[170, 90, 802, 2, 24, 45, 75, 66]	i = 6
140	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 0
141	22	[802, 90, 802, 2, 24, 45, 75, 66]	i = 1
142	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 1
143	22	[802, 2, 802, 2, 24, 45, 75, 66]	i = 2
144	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 2
145	22	[802, 2, 24, 2, 24, 45, 75, 66]	i = 3
146	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 3
147	22	[802, 2, 24, 45, 24, 45, 75, 66]	i = 4
148	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 4
149	22	[802, 2, 24, 45, 66, 45, 75, 66]	i = 5
150	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 5
151	22	[802, 2, 24, 45, 66, 170, 75, 66]	i = 6
152	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 6
153	22	[802, 2, 24, 45, 66, 170, 75, 66]	i = 7
154	23	[802, 2, 24, 45, 66, 170, 75, 90]	i = 7
217	23	[2, 24, 45, 66, 75, 90, 170, 802]	i = 0
218	22	[2, 2, 24, 45, 66, 170, 75, 90]	i = 1
219	23	[2, 24, 45, 66, 75, 90, 170, 802]	i = 1
220	22	[2, 24, 24, 45, 66, 170, 75, 90]	i = 2
221	23	[2, 24, 45, 66, 75, 90, 170, 802]	i = 2
222	22	[2, 24, 45, 45, 66, 170, 75, 90]	i = 3
223	23	[2, 24, 45, 66, 75, 90, 170, 802]	i = 3
224	22	[2, 24, 45, 66, 66, 170, 75, 90]	i = 4
225	23	[2, 24, 45, 66, 75, 90, 170, 802]	i = 4
226	22	[2, 24, 45, 66, 75, 170, 75, 90]	i = 5
227	23	[2, 24, 45, 66, 75, 90, 170, 802]	i = 5

The remaining 5 key steps follow the same pattern. Press play in the visualizer to watch every step through to the result.

Frequently Asked Questions

About Radix Sort

What is Radix Sort?

Radix Sort is a non-comparison based integer sorting algorithm. It sorts numbers by processing individual digits, grouping them by the value of each digit at each position, from least significant to most significant (or vice-versa).

How does Radix Sort work?

It uses a stable sorting algorithm, like Counting Sort, as a subroutine. It sorts the entire list of numbers based on the 1's place, then re-sorts the entire list based on the 10's place, and so on, until all digits have been processed. The stability of the underlying sort is crucial to preserve the order from previous passes.

What is the time complexity of Radix Sort?

The time complexity is O(d * (n + k)), where 'd' is the number of digits in the largest number, 'n' is the number of elements, and 'k' is the base of the number system (e.g., 10 for decimal, 256 for bytes). For a fixed number of digits, this is effectively a linear time algorithm.

What is the space complexity of Radix Sort?

The space complexity is determined by the underlying stable sort. If using Counting Sort, the space complexity is O(n + k).

What does 'LSD' vs 'MSD' Radix Sort mean?

'LSD' (Least Significant Digit) Radix Sort starts sorting from the rightmost digit and moves left. It is simpler to implement and iterative. 'MSD' (Most Significant Digit) starts from the leftmost digit and moves right, using recursion to sort buckets of numbers that have the same leading digits. LSD is more common.

Can Radix Sort be used for strings?

Yes, Radix Sort is very effective for sorting strings. In this case, the 'digits' are the characters of the string, and the sorting is done character by character, usually with a base of 256 (for ASCII characters).

Is Radix Sort a comparison-based sort?

No, it is not. It sorts by grouping elements by their digits, not by comparing them to each other, allowing it to achieve a runtime faster than O(n log n) in certain conditions.

How does Radix Sort handle numbers with different lengths?

LSD Radix Sort handles this naturally. Numbers with fewer digits are treated as if they have leading zeros. For example, when sorting by the 100s place, a number like '45' is treated as '045'.

Why must the subroutine for Radix Sort be stable?

Stability is essential. For example, after sorting by the 1's place, '25' comes before '32'. When sorting by the 10's place, if the sort is not stable, the relative order of '25' and '32' is not guaranteed to be maintained when they are grouped into buckets for '2' and '3', which would corrupt the final result.

Is Radix Sort an in-place algorithm?

No, because it relies on a subroutine like Counting Sort which requires auxiliary space, Radix Sort is not an in-place algorithm.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.