The input is an array of integers and the integers fall in the half-open range 0...k. The output is another array of the same size. We can sort the input array into the output array using a technique similar to the one we used for checking anagrams. You may use O(k) extra space.
1. Determine how many times each integer appears in the input.
2. Use the result of step 1 to determine how many elements are
less-than or equal to every element.
3. Place each number from the input into its correct
position in the output array. Hint: process the input array from back to front in this step.
Consider the following example input array:
The result of step 1 is the following array. There is a 1 in position 8 because the number 8 appeared once in the input array. There is a 0 in position 7 because 7 did not appear in the input array. There is a 2 in position 3 because 3 occurs twice in the input array.
[0, 0, 2, 2, 0, 1, 0, 0, 1]
The result of step 2 is the following array. Each slot in the array says how many elements were less than or equal to that slot number. There is a 4 is position 3 because there were 4 numbers in the input array that were less or equal to 3.
[0, 0, 2, 4, 4, 5, 5, 5, 6]
The result of step 3 should be the sorted array: