Why we can not apply counting sort to general arrays?

Question

Counting sort is known with linear time if we know that all elements in the array are upper bounded by a given number. If we take a general array, cant we just scan the array in linear time, to find the maximum value in the array and then to apply counting sort?

Answer 1

It is not enough to know the upper bound to run a counting sort: you need to have enough memory to fit all the counters.

Consider a situation when you go through an array of 64-bit integers, and find out that the largest element is 2^60. This would mean two things:

• You need an O(2^60) memory, and
• It is going to take O(2^60) to complete the sort.

The fact that O(2^60) is the same as O(1) is of little help here, because the constant factor is simply too large. This is very often a problem with pseudo-polynomial time algorithms.

Answer 2

Suppose the largest number is like 235684121. Then you'll spend incredible amounts of RAM to keep your buckets.