# How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is:

def counting_sort(input_list, max_int):

# Make a histogram array for occurences of each integer
count = [0] * (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 = [0] * 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 count histogram which gives us modified_count—an array that stores the number of items with a key less than i.

• 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).

• Can you check what is happening if you run on a smaller example such as [2,2,2,3,3]? – John L. Nov 29 '18 at 4:41
• Oops, thanks for catching that; I really appreciate it! :D I wasn't initializing the output array properly. I had output = [0] * max_int when I should've had output = [0] * len(input_list) so I was getting off-by-one errors. I fixed it in my repl and in the original question. – adnauseam Nov 29 '18 at 14:29
• Suppose you have a sorted array and you want to know how many elements are smaller than $x$. You just find the index of $x$ in the array and that's your answer. This is the same principle but in reverse. – testuser Nov 30 '18 at 15:07
• Ahhh, thank you for that insight! I was overthinking this. That's so obvious in hindsight. Much obliged! What a clever algorithm. I hope somebody may benefit from my silliness. – adnauseam Nov 30 '18 at 21:50