Why Counting Sort (and Radix Sort) don't work with Negative Numbers!

programming web dev
1

In my Counting Sort tutorial, I mentioned that for counting sort to work, the numbers should be:

  1. Made up of positive numbers (0 and greater)

  2. 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:

1474×278 8.99 KB

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 :slight_smile:

2

Just copying and pasting from the tutorial, looks like it filters out negative numbers rather than including them in the sorted output?

3 
countingSort([3, -2, 1, 400, { valueOf: _ => -10, toString: _ => 'length' }])
4

Yikes. You are right. Actually, it does something worse. It creates an empty array with the negative numbers included in the total length, but the intermediate arrays no longer work because the array[-negativeIndex] operation results in subsequent array operations failing because they don’t account for values outside of the array range.

Let me update the initial post to fully backtrack on what I had initially said :facepalm:

5

It was an interesting prompt about array subscripts in any event. I think what got me started thinking was something like, if array[-1] and array[-2] are both undefined, how could code differentiate the two for sorting purposes.

1 Like