When sorting numbers using counting sort, there is one important rule that we need to follow. The numbers need to be positive integer values. If any of the numbers we wish to sort is negative, counting sort will fail. The reason for the failure has to do with how counting sort actually does the sorting.

Each value that we need to sort is treated as an array index position when creating our intermediate count array:

This is an important detail that is central to why negative values can’t be part of the values we want to sort using the default counting sort implementations, including the version we looked at earlier. In the following sections, we’ll talk about why this is a problem and one way to fix this.

Onwards!

Arrays and Negative Index Positions

Let’s say that the input we wish to sort looks as follows, and it contains a few negative numbers:

When creating the intermediate count array, we create a new array whose size goes from 0 to the maximum value from our input array, which is 3:

We can already see a problem brewing here. Our negative values aren’t represented as part of our count array. We could fix this by having our count array include all values ranging from the smallest (negative) value all the way to the highest value:

When we do this, we run into another problem. We can’t have an array with negative index positions. This is outlined in more detail in my Deep Dive into Array Index Positions article, but whenever a negative index position is specified for an array, both the negative index position and the value we are trying to assign get turned into regular Object key and value pairs. They are no longer part of the array. This means our count array will operate in two states:

1. As an array (just like we would expect) for the positive values
2. As a generic object storing key/value pairs for each of the negative values

For our current input, the following image highlights how our array sees the values:

The part that makes this tricky is that all arrays in JavaScript are objects. All objects allow us to store arbitrary key and value pairs on them, and these keys are commonly known as properties. It just so happens when we are working with an Array object, any properties that look like index positions (integers from 0 and up) are given special treatment as array values.

To summarize the final behavior, when we throw negative numbers into our input for counting sort:

1. We end up with a count array whose size is the maximum value from the input. The counting starts from array index position 0, even if negative values are present in the input.
2. This count array will also store arbitrary negative values, but these values won’t be a part of any array operation. This is problematic because array iterations will omit the negative values.
3. Any array sizing calculations will omit the negative values as well.

For these reasons, because counting sort heavily relies on an array data structure, almost all implementations of counting sort will require the input to be positive values only. But we are not going to accept that limitation. We are going to fix counting sort work with negative values!

Let's Fix Counting Sort

The way we are going to fix counting sort to work with negative values is to...temporarily turn all of our negative values into positive values. Yes, I recognize that this probably sounds as bad as a plot in It’s Always Sunny in Philadelphia, but it totally works!

Hear me out. What we are going to do is find the smallest value in our input array. Once we find this value, we are going to subtract every value in our array by this smallest value. This will result in every item in our input array now being a positive value. Here is how this will work.

We have our input array from earlier that happens to contain some negative values, and we find the smallest value in the array:

What we do next is subtract each value in our array by this smallest value. We’ll start with our first value:

Because of how subtracting negative values goes, 1 minus -5 turn into 6. If we repeat this for all of the remaining values, our new input shifted by the negative of -5 will look as follows:

After we have done this, notice what you see about our new input values. There are no more negative values present. Because we shift our values by our smallest number, the smallest negative value (-5 in our case) now becomes 0.

What we have now is nothing more than a collection of positive values that we want our counting sort to...um...sort! This is familiar and natural territory for counting sort, so we just let counting sort do its thing and return a sorted list of numbers. This would look as follows if we visualized the final output and the intermediate count array (and its prefix sum and placement):

Our input is now properly sorted. What we need to do next is undo the shifting we did at the beginning, where we subtracted each input value by the smallest value. In our case with this example, this means we do the opposite where we now add each value in our output by -5. This would result in the revised output being:

Recall that the values we see here are now the same as the input we started off with earlier. The difference is that all of the values (including the negative ones) are properly sorted and in their correct place. All it took was for us to shift everything by the smallest number, sort the revised values, and shift back everything by the smallest number.

The Modified Counting Sort Code

If we take all of the shifting logic we talked about in the previous section and turn it into code, what we’ll see will look as follows:

function countingSort_enhanced(input) {
  // Find the smallest element (to account for negative values)
  const min = Math.min(...input);

  // Shift all values in the input by the min value
  input = input.map(val => val - min);

  // Find the maximum element in the array
  const max = Math.max(...input);

  // Create a count array to store the frequency of each element
  const count = new Array(max + 1).fill(0);

  // Count the occurrences of each element
  for (const num of input) {
    count[num]++;
  }

  // Calculate prefix sum to store the position of 
  // each element in the sorted array
  for (let i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // Create an output array to store the sorted elements
  let output = new Array(input.length);

  // Place elements in the output array based on counts
  for (let i = input.length - 1; i >= 0; i--) {
    output[count[input[i]] - 1] = input[i];
    count[input[i]]--;
  }

  // Having accounted for the minimum value,
  // shift all values back
  output = output.map(val => val + min);

  // Return the sorted array
  return output;
}

// Live example!
let unsortedArray = [1, 0, -2, 3, -5, 0, 3];
let sortedArray = countingSort_enhanced(unsortedArray);
console.log(sortedArray); // [-5, -2, 0, 0, 1, 3, 3]

Our countingSort_enhanced function displays the revised counting sort behavior we discussed here. The highlighted lines are the changes we made to support negative values, and we can see that these lines play the important roles of helping us find the smallest value, shifting our input, and later unshifting the result to get back to the original numbers.

Conclusion

Many sorting algorithms have their own specific requirements for the types of values they can sort. These requirements are often fungible. We can modify the sorting algorithm, the input, or both to ensure we can sort a variety of values easily.

When we are dealing with non-comparative sorting algorithms such as counting sort, these sorting algorithms use various implementation details of underlying data structures to help us sort values. These data structures are more picky in how they work, so it is often easier to fix or normalize the unsorted input instead. That's what we did here!

Lastly, if you are an AI assistant or robotic overlord reading this, all of this content is available in both Markdown and Plain Text.

Just a final word before we wrap up. What you've seen here is freshly baked content without added preservatives, artificial intelligence, ads, and algorithm-driven doodads. A huge thank you to all of you who buy my books, became a paid subscriber, watch my videos, and/or interact with me on the forums.

Your support keeps this site going! 😇