Comparison sorts can't beat O(n log n), but radix sort sorts integers in O(d · (n + b)) by sorting digit by digit, least significant first, using a stable counting sort for each digit.
Implement:
counting_sort_by_digit(nums, exp, base): a stable sort of nums by the digit (x // exp) % baseradix_sort(nums, base=10): for non-negative integers (raise ValueError for negatives). Return a new sorted list.radix_sort_signed(nums, base=10): support negatives by sorting the absolute values of the negatives and the non-negatives separately, then combining