DSA Complexity

Counting sort cost

Question-led: if counting sort is "linear," linear in what? n alone, or n + k?

State with k the key range. It is a sort: fast when k is affordable, impossible when k explodes.

Algorithm journey

Compute k

Fail fast if k is huge.

Theta(n) frequencies

Plus Theta(k) init.

Theta(k)

Build boundaries.

Theta(n)

Stable output write.

What actually happens

Naive claim: counting is always O(n). False: O(n + k), and k can dominate.

Better claim: check k before allocating.

Negatives need offsets; overflow of max-min must be handled.

Invariant

Every key maps into a counter index; total initialization and prefix work scale with k, placement with n.

How to read counting sort's complexity

1. Is k = O(n)? Sweet spot.

2. Is k = 10^9? Reject.

3. Feeding radix? Keep passes stable; cost multiplies by digit count.

Quantitative check

n = 10^7, k = 256: a few tens of millions of operations. n = 10^2, k = 10^9: allocation fails before asymptotics matter.

How it works

Count Frequencies

Create a count array and store the frequency of each unique element from the input.

Calculate Cumulative Counts

Modify the count array to store cumulative counts. This tells you the starting position of each element in the sorted output.

Build Output Array

Iterate through the input array, place each element at its correct position using the count array, and decrement the count.

🎮 Interactive Counting Sort Demo

Watch how the algorithm counts frequencies and reconstructs the sorted array without comparisons!

Speed:

ℹ️ Ready

Input Array

Count Array (Index = Value)

Output Array

Tip: When to Use It?

Use Counting Sort when the range of input values (k) is not significantly larger than the number of elements (n). Example: Sorting 1 million people by age (0-120) is instant. Sorting 10 numbers where values can be up to 1 billion is a bad idea (huge memory usage)!

💻 Implementation

Python

python

def counting_sort(
    values: list[int],
    max_range: int = 10_000_000,
    range_to_input_ratio: int = 64,
) -> list[int]:
    """Return a stable counting-sort result; reject unsafe key ranges."""
    if not values:
        return []

    minimum = min(values)
    maximum = max(values)
    width = maximum - minimum + 1
    dense_limit = max(1_024, len(values) * range_to_input_ratio)
    if width > max_range or width > dense_limit:
        raise ValueError("key range is too sparse for counting sort")

    counts = [0] * width
    for value in values:
        counts[value - minimum] += 1

    # Prefix sums convert frequencies into exclusive output endpoints.
    for index in range(1, width):
        counts[index] += counts[index - 1]

    output = [0] * len(values)
    # Reverse traversal preserves the order of equal-key records.
    for value in reversed(values):
        key = value - minimum
        counts[key] -= 1
        output[counts[key]] = value
    return output


if __name__ == "__main__":
    data = [4, -2, 2, 8, 3, 3, -2]
    print(counting_sort(data))

Java

java

public class CountingSort {
    private static final long MAX_RANGE = 10_000_000L;
    private static final long RANGE_TO_INPUT_RATIO = 64L;

    public static int[] countingSort(int[] values) {
        if (values.length == 0) {
            return new int[0];
        }

        int minimum = values[0];
        int maximum = values[0];
        for (int value : values) {
            minimum = Math.min(minimum, value);
            maximum = Math.max(maximum, value);
        }

        // Compute in long: max - min + 1 can overflow int.
        long widthLong = (long) maximum - minimum + 1L;
        long denseLimit = Math.max(1_024L, values.length * RANGE_TO_INPUT_RATIO);
        if (widthLong > MAX_RANGE || widthLong > denseLimit) {
            throw new IllegalArgumentException(
                    "key range is too sparse for counting sort");
        }

        int width = (int) widthLong;
        int[] counts = new int[width];
        for (int value : values) {
            int key = (int) ((long) value - minimum);
            counts[key]++;
        }

        for (int key = 1; key < width; key++) {
            counts[key] += counts[key - 1];
        }

        int[] output = new int[values.length];
        for (int index = values.length - 1; index >= 0; index--) {
            int value = values[index];
            int key = (int) ((long) value - minimum);
            output[--counts[key]] = value;
        }
        return output;
    }

    public static void main(String[] args) {
        int[] data = {4, -2, 2, 8, 3, 3, -2};
        System.out.println(java.util.Arrays.toString(countingSort(data)));
    }
}

Prefix-sum invariant and stability

After frequency counting, counts[x] is the number of occurrences of key x. After the prefix pass it is the exclusive end position for keys ≤ x. Decrementing that endpoint reserves one unique output slot, so every item is placed exactly once and all positions for smaller keys precede positions for larger keys.

Traversing input from right to left is what makes the placement phase stable: among equal-key records, the later record claims the later free slot. A frequency-only reconstruction sorts integers but does not provide a stable keyed-record primitive for radix sort or multi-key pipelines.

The real parameter is key width

Negative keys

Offset by the minimum: key index = value − min. This changes neither order nor stability.

Sparse domains

Ten values spanning billions of keys make O(k) memory unacceptable. Fall back to comparison sorting.

Overflow and allocation

Java computes width in long before allocating. Both versions reject an unsafe absolute range and density ratio.

⚡ Complexity Analysis

Time Complexity

✓
O(n + k) - All Cases
n = number of elements, k = range of input

Space Complexity

⚠
O(n + k)
Stable placement needs an n-item output plus k counters

Other Properties

✓Stable: Preserves order of equal elements
✗Not In-place: Requires extra space

✅ Pros & ❌ Cons

✅ Advantages

✓Linear time O(n+k) - faster than O(n log n) for small k
✓Stable sorting algorithm

❌ Disadvantages

✗Restricted to integer inputs (or mappable to integers)
✗Inefficient if range (k) is very large
✗Not an in-place algorithm

Production decision and verification

Use counting sort when keys are integral or cheaply mapped, k is known and dense enough, and O(n + k) memory fits the service budget.
Reuse counter/output buffers in high-throughput pipelines; repeated zero-filling and allocation can dominate small sorts.
For arbitrary records, store records in the output while counting their extracted integer keys. Stability then preserves prior secondary-key ordering.
Test empty, singleton, all equal, negative-only, mixed signs, duplicates, min/max integers, and a deliberately sparse range that must trigger the guard.
Property checks: sorted order, exact multiset preservation, stable identity order for equal keys, no input mutation, and agreement with the platform sort.

The comparison-sorting Ω(n log n) lower bound does not apply because counting sort uses key-domain addressing. If the key domain is too wide, that extra assumption stops being useful and an optimized comparison sort is the right fallback.

Exercises

Write the cost of each of the three phases in terms of n and k.
Give (n,k) where counting is asymptotically worse than mergesort.
How does stability change the placement loop's constant factors, not its Theta class?

Primary sources

CLRS: counting sort.
Knuth TAOCP Vol. 3: distribution counting.
Radix chapter: multiplying by d passes.

Short takeaway

Counting Sort = Count frequencies, calculate positions, place elements.Time: O(n + k).Space: O(n + k) for this stable implementation.Use when: Sorting integers with small range (e.g., ages, test scores).Avoid when: Range k is huge (e.g., sorting random 64-bit integers).