Understanding Linear Time Non-Comparison Sorts

Why Comparison Sorts are Limited

Before we see how to break the $O(n\log n)$ barrier, it's helpful to understand why that barrier exists for algorithms like Quicksort and Merge Sort. At their core, they rely on a compare(a, b) operation that has only two outcomes (e.g., a < b or a >= b).

To sort $n$ unique items, there are $n!$ (n-factorial) possible correct orderings (permutations). Any comparison-based algorithm must perform enough comparisons to distinguish the correct ordering from all other possibilities. This can be visualized as a decision tree where each node is a comparison, and each leaf is a permutation. To have enough leaves for all $n!$ permutations, the tree must have a height of at least ${\log }_2(n!)$, which can be shown to be in $\Omega (n\log n)$.

So, how do we do better? We need to use an operation more powerful than a simple two-way comparison.

This idea of using an element's value to directly determine its position, rather than just comparing it to other elements, is the key insight behind the algorithm we'll study today: Counting Sort.

Counting Sort: The Core Idea

Counting Sort is a non-comparison sorting algorithm that is efficient when the input consists of items (like integers) within a known, relatively small range.

Imagine you need to sort an array of integers where you know all values are between 0 and 9. Instead of comparing the numbers, you could simply:

1. Create 10 "bins," one for each possible value (0 through 9).
2. Go through the input array and place each number in its corresponding bin.
3. Concatenate the contents of the bins in order (all the 0s, then all the 1s, etc.) to get the sorted array.

This is the essence of Counting Sort. It avoids comparisons by using the element values themselves as addresses into an auxiliary data structure.

The Mechanism of Counting Sort

Now let's walk through the full, stable version of the algorithm. A stable sort preserves the original relative order of equal-valued elements. This is a desirable property, and as you'll see, it requires a bit more sophistication than the simple "bin" idea.

The algorithm assumes we are sorting $n$ integers in the range [0, k]. It involves three main passes. Let's use a detailed video walkthrough to understand each step.

Step 1: Count Frequencies

As shown in the video, the first step is to create a count array of size $k+1$. We then iterate through the input array (let's call it A) of size $n$, and for each element A[j], we increment count[A[j]]. After this pass, count[i] holds the number of elements in A equal to i.

Step 2: Calculate Cumulative Positions

This is the key step that helps place elements correctly and ensures stability. We transform the count array so that count[i] stores the number of elements less than or equal to i.

After this step, count[i] now tells us the index where the last element with value i should be placed in the sorted output array (assuming 1-based indexing, or the index after the last element in 0-based indexing).

Step 3: Build the Output Array

Finally, we build the sorted output array (let's call it B). To ensure stability, we iterate through the input array A backwards, from the last element to the first.

For each element A[j]:

1. Find its target position using the cumulative count array: pos = count[A[j]].
2. Place A[j] into the output array B at B[pos - 1] (for 0-based indexing).
3. Decrement count[A[j]] to ensure the next identical element (which we encounter because we're iterating backwards) is placed in the preceding slot.

Analysis: Achieving Linear Time

Now we can clearly see how Counting Sort achieves its impressive performance.

• Step 1 (Count Frequencies): We initialize a count array of size k+1 ($O(k)$ time) and iterate through the input array of size n once ($O(n)$ time). Total: $O(n+k)$.
• Step 2 (Calculate Cumulative Positions): We iterate through the count array once ($O(k)$ time).
• Step 3 (Build Output Array): We iterate through the input array of size n once ($O(n)$ time).

The overall time complexity is the sum of these steps: $O(n+k)$.

This is a linear time complexity! If the range k is proportional to the number of elements n (i.e., $k=O(n)$), the complexity becomes $O(n+n)=O(n)$.

Space Complexity and Limitations

The efficiency of Counting Sort comes at a cost: space. The algorithm requires an auxiliary count array of size $k+1$ and an output array of size $n$. Therefore, the space complexity is $O(n+k)$.

This leads us to the primary limitation of Counting Sort:

• It is only efficient when the range of input values, k, is not significantly larger than the number of elements, n. If you have n=100 elements but their values can go up to k=1,000,000, you would need an enormous count array, making the algorithm highly impractical in both time and space.

Other limitations include:

• It is not a general-purpose sorting algorithm, as it's designed for integers or data with integer keys.
• It doesn't directly handle negative numbers or floating-point numbers without modifications (like shifting all values to be non-negative).

Conclusion

We have successfully shown how a non-comparison sort can achieve linear time complexity. By sidestepping comparisons and using element values directly as array indices, Counting Sort provides an extremely fast way to sort data under the right conditions.

Key Takeaways:

• Non-comparison sorts can beat the $\Omega (n\log n)$ lower bound of comparison sorts by using information about the values of the elements, not just their relative order.
• Counting Sort works by counting the occurrences of each element in a given range [0, k] and using those counts to calculate the final positions of the elements.
• Its time complexity is $O(n+k)$, which is linear ($O(n)$) if the range k is on the order of n.
• Its main drawback is the space complexity of $O(n+k)$, which makes it impractical for data with a very large range of values.
• The full version of Counting Sort is stable, a property that is valuable in its own right and makes it a suitable subroutine for other algorithms like Radix Sort.

Preview of the Next Lesson:

We started today by briefly touching upon the $\Omega (n\log n)$ lower bound for comparison-based sorting. Now that we've seen a practical way to circumvent it, our next lesson will circle back and take a more formal, rigorous look at that barrier. We will mathematically prove why algorithms like Merge Sort and Quicksort cannot perform better than $O(n\log n)$ in the general case.