Offensive Security Researcher & Quantum Cryptography Analyst

Counting Sort Algorithm: A Linear-Time Sorting Technique Explained

Abdul Wahab Junaid
Counting Sort: A Linear-Time Sorting Algorithm

When I first encountered Counting Sort, what struck me most was how unlike a traditional sorting algorithm it felt. I wasn’t comparing elements to each other at all — I was counting them. That single shift in perspective is what lets Counting Sort achieve linear time, something no comparison-based algorithm can guarantee in the general case.

I think of Counting Sort as the conceptual foundation beneath Radix Sort — in fact, I use it as the subroutine inside every digit pass of Radix Sort in my other article. Understanding it well pays off twice.

History and Background

Counting Sort’s origins are tied closely to the same era of computing history as Radix Sort. I found that Harold H. Seward is generally credited with formally describing Counting Sort in 1954, in the same MIT thesis work where he described Radix Sort. The idea of tallying occurrences of values before placing them into position has an even older intuitive lineage in manual data-processing and tabulation techniques, but Seward’s formalization is what modern textbooks (including Knuth’s The Art of Computer Programming) trace it back to.

I find it fitting that Counting Sort and Radix Sort share a birthplace — they are, in a real sense, two halves of the same idea: one handles a single digit or small-range key perfectly, and the other repeats that process across multiple digit positions to handle arbitrarily large numbers.

Problem Statement

The problem I’m solving is: given an array of $n$ integers, each falling within a known and reasonably small range $[min, max]$, arrange them in sorted order.

The key constraint that makes Counting Sort applicable is that the range of values, $k = max – min + 1$, must be small enough relative to $n$ that allocating an array of size $k$ is practical. If $k$ is enormous compared to $n$, Counting Sort loses its advantage and a comparison-based sort becomes more practical.

Core Concepts

How It Works

Here is the sequence of steps I follow:

  1. Find the minimum and maximum values in the input array to determine the range $k$.
  2. Create a count array of size $k$, initialized to all zeros.
  3. Iterate through the input array once, incrementing count[value - min] for each element.
  4. Transform the count array into a cumulative (prefix sum) array, where each entry represents how many elements are less than or equal to that value.
  5. Iterate through the input array from right to left, placing each element into its correct position in an output array (using the cumulative count to determine position), then decrementing the count for that value.
  6. Copy the output array back into the original array (or return it directly).

Working Principle

The internal mechanism relies on the idea that if I know how many elements are less than or equal to a given value, I know exactly where that value’s elements belong in the final sorted array.

For instance, if count[5] = 7 after the prefix sum step, that tells me there are 7 elements in the array with value less than or equal to 5, meaning the last occurrence of value 5 belongs at index 6 (0-indexed) in the sorted output. As I place elements one at a time, I decrement the count so subsequent occurrences of the same value slot in just before the previous one — which is exactly why I must iterate backwards through the input to preserve stability.

Mathematical Foundation

Given $n$ elements and a key range of $k$ distinct values, Counting Sort performs:

Adding these together:

$$ T(n, k) = O(n + k) $$

This is the defining formula of Counting Sort. If $k = O(n)$, then:

$$ T(n, k) = O(n) $$

which is strictly better than the $\Omega(n \log n)$ lower bound that applies to comparison-based sorting — because Counting Sort isn’t a comparison sort at all, it isn’t bound by that theorem.

A quick sanity check I like to do: the total number of elements placed into the output array must equal $n$, and this is guaranteed because:

$$ \sum_{i=0}^{k-1} \text{count}[i] = n $$

which holds by construction, since every element increments exactly one count bucket.

Diagrams

Here’s a high-level flow of Counting Sort:

flowchart TD
    A[Input Array] --> B[Find Min and Max Values]
    B --> C[Create Count Array of size k]
    C --> D[Count Occurrences of Each Value]
    D --> E[Compute Prefix Sums]
    E --> F[Place Elements into Output Array Right to Left]
    F --> G[Copy Output Back to Original Array]

And a diagram illustrating how the prefix sum step converts raw counts into positions:

flowchart LR
    A["Raw counts: value -> frequency"] --> B["Cumulative sum: count[i] += count[i-1]"]
    B --> C["count[i] now means: elements <= i"]
    C --> D["Used as insertion index for placement"]

Pseudocode

COUNTING-SORT(A, n)
    min = MINIMUM(A, n)
    max = MAXIMUM(A, n)
    k = max - min + 1

    count = new array of size k, initialized to 0
    output = new array of size n

    for i = 0 to n - 1
        count[A[i] - min] = count[A[i] - min] + 1

    for i = 1 to k - 1
        count[i] = count[i] + count[i - 1]

    for i = n - 1 down to 0
        output[count[A[i] - min] - 1] = A[i]
        count[A[i] - min] = count[A[i] - min] - 1

    copy output into A

Step-by-Step Example

Let me trace through the array:

$$ [4, 2, 2, 8, 3, 3, 1, 0, 5] $$

Step 1 — Find range: min = 0, max = 8, so $k = 9$.

Step 2 — Build raw counts (index = value, since min is 0):

Value012345678
Count112211001

Step 3 — Convert to prefix sums:

Value012345678
Count124678889

Step 4 — Place elements, iterating input backwards:

Processing order: 5, 0, 1, 3, 3, 8, 2, 2, 4

Each placement uses the current count value as the (1-indexed) position, then decrements it. Working through all nine elements this way produces:

$$ [0, 1, 2, 2, 3, 3, 4, 5, 8] $$

This matches exactly what my tested C implementation outputs.

Time Complexity

I want to emphasize something here: Counting Sort has no notion of “bad input” the way QuickSort does. Its performance depends entirely on $n$ and $k$, never on the arrangement of the data. That predictability is one of the things I appreciate most about it.

Space Complexity

I need:

Total auxiliary space:

$$ O(n + k) $$

This is a real cost. If $k$ is very large relative to $n$ — say, sorting 100 integers where values range from 0 to 10 million — Counting Sort becomes impractical despite its linear-time reputation.

Correctness Analysis

I convince myself of correctness through the prefix sum invariant. After the cumulative sum step, count[v] represents exactly the number of elements in the input with value $\leq v$. This means the last occurrence of value $v$, when placed, must go to index count[v] - 1 in the (0-indexed) output array.

By iterating the input backwards and decrementing count[v] after each placement of value $v$, I guarantee:

  1. Every element lands in a position consistent with how many elements are less than or equal to it.
  2. Multiple elements with the same value get placed in consecutive positions, in the same relative order they appeared in the input (this is the stability property — the last occurrence found while scanning backwards is placed first, at the highest available slot, then earlier occurrences fill in below it, preserving original order).

Since every element is placed exactly once, and no two elements can be placed in the same output slot (each placement decrements the shared counter), the output array is a valid permutation of the input, and it is sorted by construction.

Advantages

Disadvantages

Applications

Implementation in C

Here is my tested implementation, which handles arbitrary min/max ranges (not just non-negative values starting at zero):

#include <stdio.h>
#include <stdlib.h>

// Sorts arr[] in place using Counting Sort.
// Handles negative numbers by shifting all values relative to the minimum.
void countingSort(int arr[], int n) {
    if (n == 0) return;

    // Step 1: find the range of values
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    int range = max - min + 1;
    int *count = calloc(range, sizeof(int));  // zero-initialized
    int *output = malloc(n * sizeof(int));

    // Step 2: count occurrences of each value (shifted by min)
    for (int i = 0; i < n; i++)
        count[arr[i] - min]++;

    // Step 3: convert counts into prefix sums (positions)
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    // Step 4: place elements into output, iterating backwards for stability
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // Step 5: copy the sorted output back into the original array
    for (int i = 0; i < n; i++)
        arr[i] = output[i];

    free(count);
    free(output);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1, 0, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Before sorting: ");
    printArray(arr, n);

    countingSort(arr, n);

    printf("After sorting:  ");
    printArray(arr, n);

    return 0;
}

Sample Input and Output

Input:

4 2 2 8 3 3 1 0 5

Output (verified by compiling and running the code above):

Before sorting: 4 2 2 8 3 3 1 0 5 
After sorting:  0 1 2 2 3 3 4 5 8

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version