Counting Sort

This article focuses on counting sort—a sorting algorithm that can achieve linear time complexity under certain conditions. (Don't confuse it with radix sort; here we concentrate solely on counting sort.)

Definition

Counting sort is a sorting technique that operates in linear time by leveraging an auxiliary array. Rather than comparing elements directly, it counts the frequency of each unique value in the input array and then uses these counts to determine the final sorted order.

How It Works

The main idea behind counting sort is to create an extra array (let's call it C) where each index represents a possible value from the input array A, and the value at each index represents the number of times that key appears in A. Using array C, we can then position each element of A into its correct sorted location.

The algorithm proceeds in three main steps:

1. Count how many times each element appears.
2. Compute the prefix sum of these counts. The prefix sum at each index tells us the total number of elements less than or equal to that key.
3. Iterate through the input array in reverse order to place each element into a new output array based on its position determined from the prefix sums. Reversing the order while placing elements ensures that the algorithm is stable (elements with the same value remain in their original relative order).

Why Compute the Prefix Sum?

Directly writing the elements into the output array using just the counts would not properly handle cases where the same number appears multiple times. By computing the prefix sum in our auxiliary array, we determine the final position for the last occurrence of each key. Then, when processing the input in reverse order, each duplicate element is placed in the correct unique slot, preserving the relative order of equal values.

Key Properties

Stability

Counting sort is a stable algorithm. This means that if two elements have the same value, they will remain in the same order relative to each other after sorting.

Time Complexity

The time complexity of counting sort is $\mathcal{O}(n+w),$ where ( n ) is the number of elements in the input array and ( w ) represents the range of possible values. When ( w ) is not significantly larger than ( n ), the sort runs in linear time.

Pseudocode

Below is the pseudocode for counting sort:

Python Implementation

Here’s a simple Python implementation of counting sort for beginners:

def counting_sort(arr):
    if not arr:
        return arr
 
    # Find the maximum value to determine the range of the count array
    max_val = max(arr)
    count = [0] * (max_val + 1)
    
    # Step 1: Count the frequency of each element
    for num in arr:
        count[num] += 1
 
    # Step 2: Compute the prefix sum array
    for i in range(1, len(count)):
        count[i] += count[i - 1]
 
    # Step 3: Place elements into the correct sorted position
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
 
    return output
 
# Example usage:
if __name__ == "__main__":
    sample = [4, 2, 2, 8, 3, 3, 1]
    sorted_sample = counting_sort(sample)
    print("Sorted array:", sorted_sample)

This Python function first counts the occurrences of each element, computes the prefix sum (which provides the positions), and then constructs the sorted array by processing the input list in reverse order.

Conclusion

Counting sort offers an intuitive and efficient way to sort elements when the range of the input values is limited. Its linear time complexity and stable behavior make it an excellent choice for certain scenarios, especially when compared to more general-purpose sorting algorithms.

By understanding the intuition behind counting sort and walking through its implementation, beginners can gain valuable insights into algorithm design and the trade-offs involved in sorting methods.