Counting Sort for Limited Range

Counting Sort is a non‑comparison based sorting algorithm that sorts integers by counting the number of occurrences of each distinct value. It works best when the range of possible values (max - min + 1) is not significantly larger than the number of elements. This makes it extremely efficient for limited ranges.

How It Works

• Find the range: Determine the minimum and maximum values in the input array.
• Count frequencies: Create an array of size range and increment the count for each element.
• Prefix sums (cumulative counts): Transform the count array so that each entry holds the number of elements ≤ that value.
• Build the output: Place each element into its correct sorted position using the cumulative counts, decrementing the count after placement.

Python Implementation

def counting_sort(arr):
    if not arr:
        return arr
    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1

    count = [0] * range_size
    for num in arr:
        count[num - min_val] += 1

    # Prefix sums to get positions
    for i in range(1, range_size):
        count[i] += count[i - 1]

    output = [0] * len(arr)
    # Build output from right to left to preserve stability
    for num in reversed(arr):
        idx = num - min_val
        count[idx] -= 1
        output[count[idx]] = num

    return output

# Example usage:
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))  # Output: [1, 2, 2, 3, 3, 4, 8]

Complexity

When to Use Counting Sort

• The range of possible values is small compared to the number of elements.
• You need a stable sort (equal elements retain their original relative order).
• You are sorting integers or objects that can be mapped to integer keys.

Applications

• Sorting grades (0–100) for large class sizes.
• Radix Sort uses Counting Sort as a subroutine.
• Frequency analysis and histogram generation.

Note: If the range is very large (e.g., sorting a few numbers between 0 and 10⁶), Counting Sort becomes inefficient in both time and space compared to comparison‑based sorts like Quick Sort or Merge Sort.