Is using a hash table valid in counting sort (in place of an array)?

Question

The classic counting sort example requires you to build an array of size equal to the greatest integer of your input array.

For example, if your array is [1, 6, 3, 10000, 8] you would need an array 10000 long for the counting sort.

Could this not be done in the same linear time using a hash table on the integers? Just a simple map?

In python, it'd be something like:

counting_map = {n: 0 for n in input_array}  # start by mapping all to 0
for num in input_array:
    counting_map[n] += 1

I know this really only works well for integers, but in that case is the mapping solution not superior?

Time-complexity wise, you initialize the map in O(n) time, then iterate through the array in O(n) time, then perform hashing functions on input in O(1) time. (Obviously big-O notation isn't the final determining factor of whether an algorithm is good, I just want to make sure I have the theory correct here).

Is this a good solution, or does the "original" counting sort still do something superior that I don't see? I'm also curious why a "hashmap-based counting sort" hardly returns any Google search results, making it seem like it's hardly ever used. Is the overhead of the hashing enough to outweigh its smaller memory footprint?

Answer 1

You can do that, and the construction would be O(n) with the obvious memory benefit.

With one little problem.

To output the sorted array, you'll still need to sort the hash table keys. And that problem is exactly what you were trying to solve in the first place.