Counting Sort for Limited Integer Ranges

1. The Core Idea: Sorting by Counting

Imagine you need to sort an array of integers where you know all numbers are between 0 and 9. Instead of comparing numbers to each other, what if you just counted how many 0s, 1s, 2s, etc., are in the array?

If you find there are two 0s, one 3, and four 5s, you can immediately reconstruct the sorted array: [0, 0, 3, 5, 5, 5, 5].

This is the fundamental principle of Counting Sort. It leverages the element values themselves as indices into a helper array to store counts, completely sidestepping the need for comparisons.

This simple version of the algorithm involves two main phases:

1. Counting Phase: Create a count array (often called a frequency array). Iterate through the input array and for each element x, increment count[x].
2. Reconstruction Phase: Iterate through the count array from the beginning. For each index i, write the value i into the original array count[i] times.

To see this simple but powerful idea in action, let's watch a short video that walks through the logic and a basic implementation.

This approach is intuitive and works perfectly for sorting primitive integers. Here’s a Java implementation reflecting what you just saw.

// Simplified (unstable) Counting Sort for non-negative integers
public void simpleCountSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }

    // 1. Find the maximum value to determine the size of the count array
    int max = 0;
    for (int num : arr) {
        if (num > max) {
            max = num;
        }
    }

    // 2. Create the count (frequency) array
    int[] count = new int[max + 1];
    for (int num : arr) {
        count[num]++;
    }

    // 3. Reconstruct the sorted array
    int arrIndex = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[arrIndex] = i;
            arrIndex++;
            count[i]--;
        }
    }
}

This implementation is simple and efficient. However, it has a limitation: it's not stable. A stable sort preserves the original relative order of equal elements. This property isn't important for primitive integers, but it's crucial when sorting objects with multiple properties.

2. The General & Stable Counting Sort

For interviews and more complex problems, you'll need the general, stable version of Counting Sort. This version can handle sorting objects by an integer key while preserving their original order if the keys are the same. It requires a few more steps and a separate output array.

Here’s the refined algorithm:

1. Create Frequency Array: Same as before, create count[k+1] and populate it with frequencies.
2. Create Position Array: Modify the count array so that each element count[i] stores the sum of counts up to i. After this step, count[i] tells you the position in the sorted array where the last element with value i should go. This is also known as a cumulative frequency array.
3. Build Sorted Array: Create a new output array of the same size as the input. Iterate through the input array from right to left. For each element x:
   a. Find its target position from the cumulative count array: pos = count[x] - 1.
   b. Place x in the output array: output[pos] = x.
   c. Decrement the count for that value: count[x]--. This ensures that the next element with the same value is placed one position to its left.
4. Copy Back: Copy the sorted elements from the output array back to the original array.

The backward iteration is the key to ensuring stability. Let's study an article that explains this process with excellent diagrams and code.

To solidify your understanding, here is a complete visual summary of the stable algorithm.

3. Complexity and Practical Considerations

Time and Space Complexity

• Time Complexity: O(n + k)

  • O(n) to iterate through the input array to find the max value.
  • O(n) to populate the frequency counts.
  • O(k) to calculate the cumulative sums.
  • O(n) to build the sorted output array.
  • Total: O(3n + k) which simplifies to O(n + k), where n is the number of elements and k is the range of the input values (max - min + 1).
  • This is linear time when k is on the order of n (i.e., k = O(n)).

• Space Complexity: O(n + k)

  • O(k) for the count array.
  • O(n) for the temporary output array in the stable version.

Handling Negative Numbers

A common interview follow-up is: "How would you adapt this to handle negative numbers?" The array-indexing approach fails with negative indices. The solution is to use an offset.

1. Find both the min and max values in the input array.
2. The size of the count array will be max - min + 1.
3. When counting, the index for a number x will be x - min.
4. When reconstructing the array, the value to be written is index + min.

Here's a code snippet illustrating the idea:

// Snippet for sorting arrays with negative numbers
public void countingSortWithNegatives(int[] arr) {
    if (arr.length == 0) return;

    int max = arr[0], min = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    int range = max - min + 1;
    int[] count = new int[range];

    // Phase 1: Count using offset
    for (int num : arr) {
        count[num - min]++;
    }

    // Phase 2: Modify to cumulative counts (for stable sort)
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    // Phase 3 & 4 would proceed similarly, using the offset
    // when accessing the count array and converting back.
}

Conclusion

You've just added a powerful linear-time sorting algorithm to your toolkit. While not a universal replacement for Quick Sort or Merge Sort, Counting Sort is unbeatable for its specific use case and is a favorite in coding challenges for its simplicity and speed.

Key Takeaways:

• Counting Sort is a non-comparison algorithm with a time complexity of O(n + k).
• It's highly effective when the range of input integers (k) is not significantly larger than the number of elements (n).
• The simple implementation is intuitive but not stable.
• The stable implementation is essential for general-purpose sorting of objects and is achieved by using a cumulative frequency array and iterating backward through the input.
• Handling negative numbers is a common extension, solved by using an offset (min value).

Preview of the next lesson:
We've covered a variety of sorting algorithms, each with its own trade-offs. Now, we'll shift our focus from sorting to another fundamental problem area: searching within strings. In the next lesson, we will explore string hashing and the Rabin-Karp algorithm, a clever technique that uses a "rolling hash" to find patterns in text efficiently. This is another crucial tool for your competitive programming and algorithm design arsenal.