Sorting Algorithms

Counting Sort

● Intermediate ⏱ 7 min read sorting

Counting sort is a non-comparison-based sorting algorithm that sorts integers by counting occurrences. It runs in O(n+k) where k is the value range, making it faster than O(n log n) comparison sorts when k is small relative to n.

How It Works

Text

Array: [4, 2, 2, 8, 3, 3, 1]  (values 1–8, k=8)

Step 1 — Count occurrences:
  count[1]=1, count[2]=2, count[3]=2, count[4]=1, count[8]=1

Step 2 — Prefix sums (cumulative counts):
  count[i] += count[i-1]
  count[1]=1, count[2]=3, count[3]=5, count[4]=6, ..., count[8]=7

Step 3 — Place elements in output array (right-to-left for stability):
  Process 1 → output[count[1]-1] = output[0] = 1; count[1]--
  ...
  Result: [1, 2, 2, 3, 3, 4, 8]

Basic Implementation

Python

def counting_sort_basic(arr):
    if not arr:
        return arr
    max_val = max(arr)
    count   = [0] * (max_val + 1)

    for x in arr:
        count[x] += 1

    result = []
    for val, cnt in enumerate(count):
        result.extend([val] * cnt)
    return result

nums = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort_basic(nums))   # [1, 2, 2, 3, 3, 4, 8]

Stable Version (Prefix Sums)

The basic version above is not stable. The stable version uses prefix sums to place each element in the output array at its exact final index, processing from right to left to preserve original order of equal elements.

Python

def counting_sort_stable(arr):
    if not arr:
        return arr
    max_val = max(arr)
    count   = [0] * (max_val + 1)

    # Step 1: count occurrences
    for x in arr:
        count[x] += 1

    # Step 2: prefix sums — count[i] now = number of elements <= i
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Step 3: build output right-to-left (preserves stability)
    output = [0] * len(arr)
    for x in reversed(arr):
        count[x] -= 1
        output[count[x]] = x

    return output

nums = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort_stable(nums))   # [1, 2, 2, 3, 3, 4, 8]

💡

Counting sort as a subroutine

Counting sort is used inside radix sort as a stable sort for individual digit positions. The stability guarantee ensures that multi-digit sorting (e.g. sort by units, then tens, then hundreds) produces the correct final order.

When to Use Counting Sort

Python

# Good: small range k, many elements n
# Sort exam scores 0–100 for 10,000 students
scores = [random_score for _ in range(10_000)]  # k=101, n=10000
# O(n+k) = O(10000+101) ≈ O(n) — much faster than O(n log n)

# Bad: large range k >> n
# Sort 10 phone numbers (10 digits each → k = 10^10)
# count array would need 10 billion slots — impractical

# The break-even point: counting sort wins when k < n log n
import math
n = 1000
k_threshold = n * math.log2(n)
print(f"Use counting sort if k < {k_threshold:.0f}")
# Use counting sort if k < 9966

Complexity Table

Case	Time	Space	Note
All cases	O(n+k)	O(k)	k = max value (value range)
Stable	Yes	—	With prefix-sum version
Integers only	—	—	Cannot sort floats or strings directly
When k ≫ n	Worse than O(n log n)	—	Large count array dominates