Why can't I do the counting sort this way?

Question

Counting sort is basically storing the count values in a hash-table sort of structure and then print out the values.

The method I adopted was:

1. Traverse over the input array and store the total counts by count[arr[i]]++

2. Again, traverse over the count array and print the i(th) index number as many times as the value is there in count[arr[i]]. Is this not the correct method?

Most of the places where I read the tutorial, they stored the sum of the counts of previous elements in count array and then place in sorted array by first decreasing the count and then printing it.

Is there anything wrong with my method?

Thanks!

Answer 1

Your method is fine when all objects in your array that compare the same are identical. For example, in the array [ 8, 2, 3, 5, 4, 3 ], both 3s are identical, so it doesn't matter which 3 you print twice in the sorted result. But consider the following JSON array:

[
    { "name": "apple", "quantity": 8 },
    { "name": "banana", "quantity": 2 },
    { "name": "dragonfruit", "quantity": 3 },
    { "name": "kiwifruit", "quantity": 5 },
    { "name": "pineapple", "quantity": 4 },
    { "name": "watermelon", "quantity": 3 }
]

If you sort this array by quantity, dragonfruit and watermelon will be placed in the same bin, 3. However, when looping over the bins, you can't just print dragonfruit twice to generate the sorted results. Instead, by inserting a loop in the middle of the algorithm to calculate the prefix sum for each bin, it generalizes the algorithm to operate on objects that may differ but compare as equal, and thus it prints dragonfruit once and watermelon once.

The Variant algorithms section of the Wikipedia page for counting sort mentions your optimization, saying that the second and third loops can be combined when the items being sorted are integers.