DSA — Counting Sort

What is Counting Sort?

Counts occurrences of each element and uses them to reconstruct the sorted array.

def counting_sort(arr):
    if not arr:
        return arr
    
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1
    
    count = [0] * range_val
    output = [0] * len(arr)
    
    # Count occurrences
    for num in arr:
        count[num - min_val] += 1
    
    # Cumulative count
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # Build output
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    
    return output

Time Complexity

Case	Complexity
Best	O(n + k)
Average	O(n + k)
Worst	O(n + k)

Where k is the range of input.

Characteristics

• Stable sort
• Not comparison-based
• Works with integers
• Limited by range of values

Mini Practice

1. Implement counting sort
2. Sort with negative numbers
3. Use for string sorting
4. Compare with comparison sorts

Up Next

Continue with Radix Sort — digit-by-digit sorting.