Radix Sort for Non-Negative Integers

Given an array of n non-negative integers, sort them into non-decreasing order using Radix Sort: repeatedly apply a stable counting sort on each digit position, starting from the least significant digit and moving toward the most significant digit. Return the fully sorted array.

Input: The first line contains an integer n. The second line contains n space-separated non-negative integers. Output: Print the n integers sorted in non-decreasing order, space-separated, on a single line.

1 <= n <= 8000 0 <= a[i] <= 1000000

Radix sort is a rare example of a sorting algorithm that AVOIDS direct element-to-element comparisons entirely, which is exactly why it can beat the O(n log n) comparison-sort lower bound under the right conditions (small digit count relative to n).

Sort non-negative integers by processing one digit position at a time, from least to most significant. Brute force: Use a general comparison-based sort (like merge sort or quicksort) directly - this works and costs O(n log n), but radix sort can beat this when the number of digits is small relative to n, achieving closer to linear time. Optimised: Since STABLE counting sort preserves relative order from the PREVIOUS pass, processing digits from least to most significant means that by the time the MOST significant digit is sorted, all the less-significant digit orderings established earlier are still correctly preserved as tie-breakers - this achieves a full sort without ever directly comparing two numbers to each other.

1. Process numbers digit by digit, starting from the LEAST significant digit and moving toward the most significant. 2. For each digit position, apply a STABLE counting sort (one that preserves the relative order of equal elements) as the sorting subroutine. 3. Stop once the current digit position exceeds the most significant digit of the largest number in the array.

Time: O(d * (n + b)), where d is the number of digits and b is the base (10 for decimal) - each of the d digit passes costs O(n+b) for its counting sort subroutine. Space: O(n + b), for the counting sort's auxiliary arrays.

All numbers could be identical (including all being zero), or the numbers could have very different digit lengths (single-digit alongside seven-digit values).

Be ready to explain WHY the counting sort subroutine must be STABLE - an unstable subroutine would scramble the ordering established by earlier, less-significant digit passes, breaking the whole algorithm's correctness.