Counting Sort: The Algorithm That Skips the Comparisons

📘 Introduction

In the world of sorting algorithms, we often hear about Merge Sort, Quick Sort, or even Bubble Sort. But there's one algorithm that quietly delivers blazing-fast performance under the right conditions—Counting Sort. Unlike comparison-based algorithms, Counting Sort leverages the power of integer keys and frequency counting to achieve linear time complexity. Let’s unpack its brilliance.

🧠 The Idea Behind Counting Sort

Counting Sort works best when:

• The input consists of integers within a known, limited range.
• The goal is to sort without comparisons.

Instead of comparing elements, it counts how many times each value appears, then uses that information to place elements directly into their sorted positions.

Think of it like organising exam papers by roll number. You don’t compare papers—you just place each one in its designated slot.

⚙️ Algorithmic Steps

Here’s how Counting Sort works step-by-step:

1. Find the range of input values (min and max).
2. Initialise a count array of size max - min + 1.
3. Count occurrences of each value.
4. Modify the count array to store cumulative counts.
5. Build the output array by placing elements at their correct positions.
6. Copy the output back to the original array (if needed).

💻 Counting Sort Implementation

def counting_sort(arr):
    if not arr:
        return arr

    min_val = min(arr)  # min_val = 1
    max_val = max(arr)  # max_val = 8
    range_size = max_val - min_val + 1  # range_size = 8

    count = [0] * range_size  # count = [0, 0, 0, 0, 0, 0, 0, 0]
    output = [0] * len(arr)   # output = [0, 0, 0, 0, 0, 0, 0]

    # Step 1: Count occurrences
    for num in arr:
        count[num - min_val] += 1

    # Step 2: Cumulative count
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Step 3: Build output array (stable sort)
    for num in reversed(arr):
        count[num - min_val] -= 1
        output[count[num - min_val]] = num
    # output after sorting = [1, 2, 2, 3, 3, 4, 8]

    return output

# Example
arr = [4, 2, 2, 8, 3, 3, 1]
print("Sorted array:", counting_sort(arr)) 

# Output: 
Sorted array: [1, 2, 2, 3, 3, 4, 8]        

📊 Time & Space Complexity

• Time Complexity (Best/Average/Worst) = O(n + k) 
• Space Complexity: O(n + k)

n = number of elements

k = range of values (max − min)

⚖️ Strengths & Weaknesses

✅ Strengths:

• Linear time for small ranges
• Stable sort (preserves input order)
• Great for sorting integers, characters, or categorical data

❌ Weaknesses:

• Not suitable for large ranges (e.g., sorting ages from 1 to 1,000,000)
• Only works with discrete, countable keys (integers or mappable categories)
• Extra space usage for count array

🔑 Key Takeaways

• Counting Sort is a powerful tool when the input range is limited and known.
• It’s ideal for sorting data like grades, ages, or categorical labels.
• Although not suitable for all use cases, Counting Sort performs exceptionally well in specific scenarios where traditional comparison-based algorithms are less efficient.