def counting_sort(input_list, max_int): # Make a histogram array for occurences of each integer count =  * (max_int + 1) for i in range(len(input_list)): value = input_list[i] count[value] += 1 # count -> [0, 2, 2, 0, 0, 1, 1, 1] # Prefix sum the count histogram array modified_count = [i for i in count] for i in range(1, len(count)): modified_count[i] = modified_count[i-1] + modified_count[i] # modified_count -> [0, 2, 4, 4, 4, 5, 6, 7] # Output elements from input_list according to modified_count output =  * len(input_list) for i in range(len(input_list)): output_value = input_list[i] output_index = modified_count[output_value] - 1 output[output_index] = output_value modified_count[input_list[i]] -= 1 print("Output", output) counting_sort([1,5,7,6,2,1,2], 7)
Most of this algorithm makes sense to me:
- The algorithm makes a histogram of occurrences where
count[i]is the number of occurrences.
Then we prefix sum this
counthistogram which gives us
modified_count—an array that stores the number of items with a key less than
We then use that array to determine the index of the integer in the output array.
The Wikipedia article states, that the
modified_count array, which stores the number of items with a key less than
i, is the same as an array where each item is the "the first index at which an item with key
i should be stored in the output array."
That quote from Wikipedia is what I don't understand.
In a nutshell, my question is: Why is the number of items with a key less than
i the same as the first output array index for an item with key
i. It seems so clever, but very mystifying (currently).