In my Counting Sort tutorial, I mentioned that for counting sort to work, the numbers should be:
-
Made up of positive numbers (0 and greater)
-
The range between the smallest and the largest number needs to be fairly small, around the same order of magnitude as the input size
When it comes to #1, the answer to why it doesn’t work can be explained here: Diving Deep into Array Index Positions
When our arrays encounter a negative index position caused by a negative value we are trying to sort, JavaScript works just fine. The reason is that, while negative index positions aren’t valid, they end up being treated like object keys/properties.
Look at the following image where we have -2 as a key on our people
array:
This is also the problem. While JavaScript is OK with what look like negative index positions, they don’t work with the array behavior of Arrays. This means our intermediate arrays, created as part of Counting Sort, store the negative value. These values are stored as non-array key/value pairs, so they don’t get picked up by array operations.
Cheers,
Kirupa