Counting Sort

Concept

In computer science, it is mathematically proven that any sorting algorithm that compares two elements (A < B) cannot be faster than $O(N \log N)$.

Counting Sort breaks this barrier, achieving linear $O(N)$ time!
How? By completely refusing to use if (A < B).
Instead, it exploits the fact that the array contains integers. It counts the frequencies of those integers, and uses their mathematical values as direct array indexes.

The Mechanism

You are given an array of ages to sort: [5, 2, 5, 1, 2].
You know mathematically that nobody is older than 5.

1. The Frequency Array: Create a massive empty array called counts ranging from index 0 to index 5.
2. Count: Loop through the input array once.
   • Found a 5? counts[5]++.
   • Found a 2? counts[2]++.
   • Found another 5? counts[5]++.
3. Rebuild: After one pass, the counts array looks like this:
   • Index 0: 0
   • Index 1: 1
   • Index 2: 2
   • Index 3: 0
   • Index 4: 0
   • Index 5: 2
     By simply looping left-to-right through the counts array, you know exactly what the sorted output should be! Write out one 1, two 2s, and two 5s: [1, 2, 2, 5, 5].

Implementation

// Time Complexity: O(N + K) (Where N is array length, K is the Maximum value)
// Space Complexity: O(K) (The size of the counts array)

function countingSort(nums: number[]): number[] {
    if (nums.length === 0) return [];

    // 1. Find the maximum value in the array to size our Counting array
    let max = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > max) max = nums[i];
    }

    // 2. Initialize the frequency counts array with zeros
    const counts = new Array(max + 1).fill(0);

    // 3. Tally the frequencies (No comparisons!)
    for (let i = 0; i < nums.length; i++) {
        counts[nums[i]]++;
    }

    // 4. Rebuild the final sorted array
    let outputIndex = 0;
    for (let i = 0; i < counts.length; i++) {
        // While we still have counts of the number 'i'...
        while (counts[i] > 0) {
            nums[outputIndex] = i; // Overwrite the original array in-place!
            outputIndex++;
            counts[i]--;
        }
    }

    return nums;
}

The Fatal Flaw

Counting Sort is blazing fast, but it has devastating limitations.

1. It only works on Integers.
You cannot use Counting Sort on strings ("Apple"), floats (3.14), or objects ({name: "Alice"}), because you cannot use a string or a decimal as a direct array index!

2. The Range K Memory Explosion.
Notice the Space Complexity is $O(K)$, where K is the absolute largest number in the array.
If you give Counting Sort an array of exactly two numbers: [1, 999999999].
To sort these two numbers, it will initialize a massive counts array of 1 Billion empty slots in RAM, immediately crashing the computer with an Out of Memory error.

Counting Sort is strictly reserved for scenarios where you are sorting a massive amount of data, but the integers themselves are bound to a very small, known range (e.g., Sorting 1 Million people by Age 0 - 120, or sorting 10 Million exam scores 0 - 100).

Interview Questions

Q: Can Counting Sort handle negative numbers? [-5, 2, -1]
A: The standard implementation crashes immediately, because you cannot do counts[-5]++ (Negative Array Indexes don’t work). However, you can mathematically offset the array. You find the minimum value (-5), and you shift every single element upward by +5. -5 becomes index 0. 2 becomes index 7. You perform the count, and when rebuilding the array, you subtract the offset back off.

Q: Is Counting Sort Stable?
A: The basic implementation shown above is Unstable (because it violently overwrites the original objects with fresh integers). However, in FAANG interviews, you must know that Counting Sort CAN be made Stable. By mathematically calculating the “Prefix Sums” of the counts array, you calculate the exact final ending index of every element. You then iterate the original array backwards, perfectly placing the objects into their mathematically assigned slots, achieving perfect Stability. (This stable version is the required core engine used inside Radix Sort!).