loading
loading
loading
Computer Science / Algorithms
Repeated Counting Sort passes, one per digit, least significant first — builds on Counting Sort's bucket pattern.
Radix sort sorts multi-digit numbers one digit position at a time, starting from the ones place and working up — this demo's specific choice is LSD (least-significant-digit-first), base-10 radix sort; MSD (most-significant-first) and other bases exist but aren't implemented here. Each digit position is sorted using exactly the same count-then-place idea Counting Sort uses, with 10 buckets (digits 0–9) instead of one bucket per value. The one requirement that makes the whole algorithm correct: every digit pass must be stable — it must never disturb the relative order that earlier, less-significant-digit passes already established between two numbers sharing this digit. This demo's per-pass sort is stable by construction: it scans the array left to right, appending each number to its digit's bucket in the order encountered, then drains the buckets 0 through 9 back into the array — nothing ever gets reordered within a bucket. Watch the bucket histogram (reusing Counting Sort's exact bar pattern) fill during each pass's distributing phase and drain during its collecting phase, with the current pass and digit position always shown above. Press Shuffle to generate a new random array and watch the multi-pass process repeat.
Because later passes rely on the ordering earlier passes already produced. After the ones-digit pass, every number with the same ones digit is grouped together in their original relative order — the tens-digit pass then only needs to sort by the tens digit, trusting that ties (same tens digit) stay in the order the ones-digit pass left them in. If a pass weren't stable, it could scramble that trusted order, and the final result would be wrong, not just differently arranged. That's why this radix sort visualizer, unlike this platform's Counting Sort demo, cannot use the simpler non-stable placement — stability here is a correctness requirement, not a nice-to-have.
Directly: each of radix sort's d digit passes is one full counting sort over 10 buckets, costing O(n + 10) — so d passes cost O(d · (n + 10)), or O(d · n) for a fixed base. Radix sort is, structurally, just Counting Sort applied repeatedly, once per digit.
LSD radix sort is the simpler of the two to reason about and implement correctly: process digits ones-first, and by the time you reach the most significant digit, everything below it is already correctly ordered and stable, so that one final pass finishes the job. MSD radix sort (most-significant-digit-first) can be faster in some cases but requires recursively sub-sorting each bucket rather than a flat sequence of full passes — not implemented here.