Radix Sort
Non-comparative sorting algorithm that processes the digits of numbers from least significant to most significant.
Ready to sort
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Think of sorting a large pile of files by date (Year-Month-Day). You wouldn't compare every file to every other file. Instead, you would first sort them all into piles by Day (1-31). Then, stack them up and sort them again by Month (Jan-Dec). Finally, sort by Year. After this, the whole pile is perfectly sorted. This is Radix Sort: sorting column by column.
Concept
Radix Sort 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.
How it Works
Algorithm:
- Find the maximum number to know the number of digits.
- Do a stable sort (usually Counting Sort) for every digit place
exp(1, 10, 100...). - Start from the Least Significant Digit (LSD).
- Move to the next digit place and repeat.
Step-by-Step Breakdown
Watch the visualization:
- Blue Highlight: Processing the digit at current place (Ones, Tens, etc).
- Colors: Indicate which bucket/value is being counted or moved.
- Passes: Each full sweep of the array represents sorting by one digit place.
When to Use
- Fixed Length Keys: Like phone numbers, ID numbers, or integers where
d(digits) is small. - Large Lists: Can be faster than Quick Sort (O(n)) when keys are short.
When NOT to Use
- Variable Length Strings: Requires padding, which can waste space/time.
- Space Limited: Requires auxiliary buffers for the buckets/counting sort step.
How to Identify
Look for "Sort an array of integers" where n is large (e.g., 10^5) but the range of values is constrained or comparable to n.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.