Radix Sort

Sort a list of non-negative integers using the LSD radix sort algorithm.

radix-sort sorting counting-sort stable-sort

Implement the function `radix_sort(nums)` that takes a list of non-negative integers and returns a new list sorted in ascending order using the Least Significant Digit (LSD) radix sort algorithm.

Your implementation must follow the radix sort approach:
- Determine the maximum number to know the number of digit passes.
- For each digit position (1s, 10s, 100s, ...), perform a stable sort of the list based on that digit.
- Use counting sort (or a similar stable digit-based sort) as the subroutine.

The function should not modify the input list. It should return a new sorted list. You may assume all inputs are non-negative integers. The algorithm must run in O(k * n) time where k is the number of digits of the largest number, and use O(n + 10) space per pass.

Do not use Python's built-in `sorted()` or `list.sort()` for the final result; the point is to implement the radix sort yourself. You may use auxiliary lists and simple counting.

Constraints

- `0 <= len(nums) <= 10000`
- Each element is a non-negative integer `0 <= x <= 10^9`
- Time: O(k * n), where k is the number of digits of the maximum number.
- Space: O(n + 10) per pass.

Example

>>> radix_sort([170, 45, 75, 90, 2, 24, 802, 66])
[2, 24, 45, 66, 75, 90, 170, 802]
>>> radix_sort([5, 5, 1, 3, 1])
[1, 1, 3, 5, 5]
>>> radix_sort([])
[]
>>> radix_sort([0, 0, 0])
[0, 0, 0]

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start by finding the maximum number to know how many digit passes you need; use a while loop that divides by 10 each pass.

For each pass, use counting sort with 10 buckets (digits 0-9) to stably reorder the list based on the current digit.

When extracting a digit, use `(num // exp) % 10` where exp is 1, 10, 100, ... for each pass.

Remember to build the sorted output for each pass and then assign it back to the working list; the loop ends when exp exceeds the maximum value.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.