The Counting Clerk: Sort IDs in O(n) Using Counting Sort

In the ID office of Prime City, the Clerk receives thousands of citizen IDs each day. The IDs are small non-negative integers, and the Clerk needs to sort them in O(n) time. Counting sort is the perfect algorithm: count the frequency of each ID, then reconstruct the sorted array. "Counting sort works when the range of values is small compared to the number of elements," the Clerk explains. "Count how many times each value appears, compute prefix sums for positions, then place each element in its correct sorted position." Given an array of N non-negative integers where each value is in the range [0, K], sort the array using counting sort. Output the sorted array, space-separated. Constraints: 1 <= N <= 10^6, 0 <= array[i] <= 10^4 Input: 5 4 2 2 8 3 Output: 2 2 3 4 8 Input: 3 1 0 1 Output: 0 1 1