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

  • $\begingroup$ Can you check what is happening if you run on a smaller example such as [2,2,2,3,3]? $\endgroup$ – Apass.Jack Nov 29 '18 at 4:41
  • $\begingroup$ 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. $\endgroup$ – adNauseam Nov 29 '18 at 14:29
  • $\begingroup$ 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. $\endgroup$ – testuser Nov 30 '18 at 15:07
  • $\begingroup$ 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. $\endgroup$ – adNauseam Nov 30 '18 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.