"Mahit Gupta" [email protected] wrote:

Just curious, can count sort handle negative numbers, if so how cause we only leaned how to make an array from 0 to n and even if i think about it, I can't think of a way to implement an array which accounts for -ve ints as we are only making an array of size max. Lets say we have a list only of -ve integers then what?

Counting sort just requires us to be able to count how many of each category of element appear. So we just need a data structure for that. The range [0, n) is easy as that can be done with a list of length n. But for any range [lwr, upr) we just need to be able to store upr - lwr counts. We can do this by simply offsetting the array index, so instead of counts[i] counting the number of occurrences of i, it counts the number of occurrences of lwr + i. If lwr is negative this still works. To find the index for a value is just i = val - lwr.

Alternatively we could use a data structure like a dictionary to let us use the negative values as an index directly, but this comes with significant overhead compared to just subtracting lwr from each index.