Radix Sort Visualizer

Radix sort solves counting sort's fatal problem. Counting sort is linear but needs memory proportional to the value range, which makes sorting large integers impossible. Radix sort keeps the linear behaviour and drops the memory requirement by never looking at a whole number at once — it sorts by one digit at a time, and a digit only has ten possible values no matter how big the number is.

It is also older than electronic computing. Herman Hollerith used it on punched-card tabulating machines in the 1880s, physically sorting cards into ten bins by one column, stacking them back up, and repeating with the next column. The algorithm has not changed.

What is radix sort?

Radix sort processes numbers digit by digit, using a stable sort for each pass. The LSD (least significant digit) variant — the one implemented here and the one used in practice — starts with the ones column, then the tens, then the hundreds, until every digit position has been processed.

Each pass uses counting sort on a single digit. Since a decimal digit ranges over 0–9, that inner sort needs a count array of exactly ten entries, regardless of whether the numbers being sorted are three digits long or nine. The memory problem simply disappears.

After d passes, where d is the number of digits in the largest value, the array is fully sorted. The number of passes depends on the *width* of the numbers, not on how many there are, which is why radix sort's cost is O(d·(n + k)) rather than anything involving log n.

Why it works

The whole algorithm rests on one property: each pass must be stable. Sorting by the tens digit must preserve the ordering that the ones-digit pass established, otherwise the earlier work is destroyed.

The induction is straightforward. After the first pass, the array is sorted by the last digit. Assume after pass i the array is correctly sorted by the last i digits. Pass i+1 sorts by digit i+1; elements with different digits there are ordered correctly by that digit alone, which dominates. Elements with the *same* digit at position i+1 are left in their existing relative order by stability — and that existing order is, by the inductive hypothesis, correct on the lower i digits. So the array is now sorted on the last i+1 digits.

After d passes, i+1 = d covers every digit, and the array is sorted.

Step-by-step walkthrough

Take [170, 45, 75, 90, 802, 24, 2, 66]. The largest value has three digits, so three passes are needed.

1. Pass 1 — ones digit (170→0, 45→5, 75→5, 90→0, 802→2, 24→4, 2→2, 66→6). Stable-sorted by that digit: [170, 90, 802, 2, 24, 45, 75, 66]. Note 170 stays before 90, and 802 before 2 — both had equal digits, so stability kept their input order.
2. Pass 2 — tens digit (170→7, 90→9, 802→0, 2→0, 24→2, 45→4, 75→7, 66→6). Result: [802, 2, 24, 45, 66, 170, 75, 90].
3. Look at 802 and 2 again: still in that order, since both have tens digit 0 and the previous pass left them that way — and it happens to be the correct order on the lower digits.
4. Pass 3 — hundreds digit (802→8, 2→0, 24→0, 45→0, 66→0, 170→1, 75→0, 90→0). Result: [2, 24, 45, 66, 75, 90, 170, 802].
5. The five values with hundreds digit 0 keep their pass-2 order, which was already correct on their lower two digits. Sorted.

LSD versus MSD

LSD radix sort starts from the least significant digit. It processes every element in every pass, requires no recursion, and is what almost all integer radix sorts use. Its cost is fixed and predictable: exactly d full passes.

MSD radix sort starts from the most significant digit and recurses into each bucket separately. Its advantage is early termination — once a bucket contains a single element, or a group is already distinguished by its leading digits, there is no need to examine the rest. This makes MSD the right choice for variable-length keys, particularly strings, where you want to stop as soon as words are distinguished rather than padding everything to a fixed width.

MSD is how you would sort a dictionary: all the A words together first, then subdivide within them. LSD would sort by last letter first, which feels absurd for words and works perfectly for fixed-width numbers.

Choosing the base

Base 10 is used for teaching because digits are readable. Real implementations almost always use a power of two, most often base 256 — one byte per pass.

The reason is that digit extraction becomes free. Getting the i-th decimal digit needs a division and a modulo; getting the i-th byte is a shift and a mask, which are single CPU instructions. A 32-bit integer takes four passes with byte-wise radix, against ten with decimal digits, and each pass is cheaper too.

The trade is memory: base 256 means a count array of 256 entries per pass rather than 10. That is 1 KB, which is nothing, and it fits comfortably in L1 cache. Larger bases keep reducing the pass count — base 65,536 sorts a 32-bit integer in two passes — but the count array grows to a size that no longer fits in cache, and the gains reverse. Byte-wise is the usual sweet spot.

How the animation above works

The visualiser uses base 10 so each pass corresponds to a digit position you can reason about. Values are two digits, so it completes in two passes — watch for the pass indicator in the statistics.

The instructive moment is after the first pass. The array will look *almost* random, because it is sorted only by the last digit — 21 sits before 32, but so does 41. Nothing about the display suggests progress has been made. Then the second pass runs and the array snaps into order. Radix sort produces almost no visible improvement until the final pass, which makes it the least satisfying algorithm to watch and one of the most interesting to understand.

Time complexity

O(d·(n + k)) in every case, where d is the number of digits in the largest value, n is the element count, and k is the base. There is no best or worst case — the arrangement of the input has no effect at all.

With d and k both treated as constants — which is reasonable for fixed-width integers, where a 32-bit value is always four byte-passes — this reduces to O(n). That is genuinely linear, and it is faster than any comparison sort for large arrays of fixed-width integers.

The comparison with O(n log n) deserves care, though. d is roughly log_k(max value), so for n distinct values d is at least log_k(n). Substituting gives something close to n log n, which is why radix sort does not violate any theorem. It wins in practice because its constant factor is tiny — a shift, a mask and an array write per element per pass — and because for realistic data d is fixed by the integer width rather than growing with n.

Space and stability

O(n + k) auxiliary space: an output array of size n plus a count array of size k, both reused across passes. Since k is a small constant (10 or 256), this is effectively O(n) — the same as merge sort, and the main reason radix sort is not always preferred.

Stable, necessarily and by construction. Its correctness depends on the stability of the per-digit sort, so a radix sort that is not stable is not a radix sort — it is just wrong.

Negative numbers need explicit handling, since the digit-extraction arithmetic assumes non-negative values. The two standard approaches are to partition negatives out, sort their absolute values, reverse them and prepend; or to offset every value by the minimum so everything becomes non-negative. Signed integers in two's complement can also be handled by flipping the sign bit and sorting as unsigned.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Radix Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * LSD radix sort, base 10. O(d * n) for d-digit numbers.
 * Each pass is a stable counting sort on one digit — stability is what makes
 * the passes compose into a correct sort.
 */
function radixSort(arr) {
  if (arr.length === 0) return arr;

  const max = Math.max(...arr);
  for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
    countingSortByDigit(arr, place);
  }

  return arr;
}

function countingSortByDigit(arr, place) {
  const count = new Array(10).fill(0);

  for (const value of arr) count[Math.floor(value / place) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];

  const output = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / place) % 10;
    output[--count[digit]] = arr[i];
  }

  for (let i = 0; i < arr.length; i++) arr[i] = output[i];
}

console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]));

Advantages and disadvantages

Real-world applications

• GPU and massively parallel sorting, where radix sort's branch-free regularity makes it the dominant choice.
• Sorting large volumes of fixed-width keys in databases and column stores — integer IDs, timestamps, hashes.
• Suffix array construction for text indexing and bioinformatics, where DNA sequences map onto a four-symbol alphabet.
• Network packet processing, sorting or bucketing by IP address, which is a fixed-width integer in disguise.
• Sorting strings of bounded length, using MSD radix sort with early termination once keys are distinguished.
• Historically, mechanical punched-card tabulation — the original application, and structurally identical to the modern algorithm.

Interview questions

The questions that actually get asked about Radix Sort, with the answers an interviewer is listening for.

1. Q1. Why must the per-digit sort inside radix sort be stable?

   Because each pass must preserve the ordering established by all previous passes. When two elements have the same digit at the current position, their relative order encodes the fact that they were already correctly sorted on the lower digits. An unstable sort is free to reorder them, destroying that information — radix sort with an unstable inner sort produces garbage.

2. Q2. Does radix sort violate the O(n log n) lower bound?

   No, for two reasons. First, the bound applies only to comparison-based sorts, and radix sort compares nothing — it uses digits as indices. Second, its complexity O(d·n) hides a dependency: to have n distinct values you need d ≥ log_k(n) digits, so the bound is respected in substance. It wins in practice because d is fixed by the integer width, not by n, and its constant factor is very small.

3. Q3. What is the difference between LSD and MSD radix sort?

   LSD starts at the least significant digit and makes exactly d full passes over the whole array, needing no recursion — ideal for fixed-width integers. MSD starts at the most significant digit and recurses into each bucket, which allows early termination once a group is distinguished. MSD suits variable-length keys such as strings, where padding everything to a fixed width would be wasteful.

4. Q4. Why do real implementations use base 256 rather than base 10?

   Because digit extraction becomes a shift and a mask instead of a division and a modulo — single instructions rather than expensive arithmetic. It also cuts a 32-bit integer from ten passes down to four. The cost is a 256-entry count array instead of 10, which is a kilobyte and fits easily in L1 cache. Going much larger stops paying off once the count array leaves cache.

5. Q5. How would you radix-sort an array containing negative numbers?

   Three options. Partition the negatives out, sort their absolute values, reverse and negate them, then prepend to the sorted positives. Or offset every value by the minimum so everything is non-negative, then subtract the offset afterwards. Or, for two's-complement integers, flip the sign bit before sorting as unsigned and flip it back after — this is the cleanest, since it preserves order in a single XOR.

Common mistakes

• Using an unstable sort for the per-digit pass, which breaks the algorithm entirely while still looking plausible on small examples.
• Iterating forwards in the placement loop, which makes the pass unstable and produces the same failure.
• Looping over a fixed number of digits instead of deriving it from the maximum value, which either truncates large values or wastes passes.
• Writing the loop condition as place < max rather than max / place > 0, which overflows for large values and skips the final digit.
• Feeding negative numbers into a digit-extraction routine that assumes non-negative input, producing negative bucket indices.
• Copying the output back into the input every pass instead of swapping the two array references, which doubles the memory traffic.
• Applying it to floating-point values directly — IEEE 754 bit patterns do not sort as unsigned integers without transforming the sign and exponent.

Optimisation tips

• Use base 256 and byte-wise extraction: shifts and masks instead of division, and four passes for a 32-bit integer.
• Swap the array and buffer references between passes rather than copying back — this halves the memory traffic for free.
• Skip a pass entirely when every element has the same digit at that position; a quick check of the count array reveals it immediately.
• Derive the pass count from the actual maximum rather than the type width, so an array of small values does not pay for four passes.
• For strings and other variable-length keys, use MSD with early termination rather than padding to a fixed width.
• For small arrays, do not use radix sort at all — insertion sort wins below a few dozen elements, since radix pays a fixed d-pass cost regardless of n.

Summary

Radix sort sorts numbers one digit at a time, least significant first, using a stable counting sort for each pass. Because a digit has only k possible values regardless of how large the number is, it keeps counting sort's linear behaviour without counting sort's dependency on the value range. After d passes over d-digit numbers, the array is sorted.

Everything depends on each pass being stable, which makes radix sort the clearest practical argument for why stability matters. It is O(d·n) with no worst case and a very small constant factor, which makes it the fastest option for large arrays of fixed-width integers and the standard algorithm for GPU sorting. Its limits are real, though: it needs O(n) extra space, works only on digit-decomposable data, and requires explicit handling for negatives and floats.

Frequently asked questions

Related algorithms

• Counting Sort

  Count how many times each value occurs, then write the output straight from the tallies.

  O(n + k)Intermediate

• Merge Sort

  Split the array down to single elements, then merge sorted halves back together.

  O(n log n)Intermediate

• Quick Sort

  Partition around a pivot so everything smaller lands left and larger lands right.

  O(n log n)Intermediate