Counting Sort Algorithm: Working, Explanation, and Linear Time Sorting

I want to start with counting sort because it breaks the rule most people assume applies to every sorting algorithm: it never compares two elements to decide their order. Instead, I count how many times each value appears in the input and use that count to figure out exactly where each element belongs in the final sorted array. This makes counting sort extremely fast for the right kind of data — specifically, when I am sorting integers (or things that map cleanly to integers) within a known, reasonably small range. I care about this algorithm because it shows me that the comparison-based lower bound of O(n log n) is not a law of nature — it only applies to algorithms that sort by comparing elements.

History and Background

Counting sort’s roots go back to the 1950s, tied to the broader development of non-comparison sorting techniques used in early computing and punch-card tabulation systems, where sorting by digit or by category was a physical, mechanical process long before it was a programming exercise. The technique was formalized and popularized in computer science literature through Harold H. Seward’s 1954 MIT thesis, where he described counting-based sorting as a building block for what would later be refined into radix sort. Over time, computer scientists such as Donald Knuth documented and analyzed it rigorously in The Art of Computer Programming, cementing it as a standard topic in algorithm education. I find it interesting that counting sort predates most of the comparison-based sorts that dominate textbooks today, even though it is usually taught after them.

Problem Statement

I need to sort a collection of elements, but I want to avoid the O(n log n) floor that comparison-based sorts are stuck with. The problem counting sort solves specifically is: given an array of n integers where every value falls between a known minimum and maximum (a range k), how do I sort them in linear time, O(n + k)? The catch I have to accept is that this only works efficiently when k is not dramatically larger than n — if my range is huge compared to my data size, counting sort becomes wasteful in both time and memory.

Core Concepts

A few terms I always keep straight when I think about counting sort:

• Key: the value I am sorting by, which must be a non-negative integer or something reducible to one (like a character’s ASCII code).
• Range (k): the span between the smallest and largest key values in my input.
• Count array: an auxiliary array of size k+1 where I tally how many times each key occurs.
• Cumulative (prefix) sum: I transform my count array so that each index tells me how many elements are less than or equal to that key — this is what gives each element its final position.
• Stability: counting sort, when implemented carefully (placing elements from the end of the input backward), preserves the relative order of elements with equal keys.

How It Works

I break the algorithm into four clear stages:

1. I find the range of my input by locating the minimum and maximum values.
2. I build a count array and, for every element in my input, I increment the count at the index corresponding to its value.
3. I convert this count array into a cumulative array, where each position holds the sum of all counts up to and including that index. This tells me the last position each value should occupy in the output.
4. I iterate through my original array from the last element to the first, placing each element into its correct position in the output array using the cumulative count, then decrementing that count by one.

Working Principle

The internal logic hinges on a simple but powerful idea: if I know exactly how many elements are less than or equal to a given value, I know exactly where that value’s last occurrence belongs in the sorted output. By walking my input in reverse and placing each element at the position indicated by the cumulative count, then decrementing, I naturally place duplicate values right next to each other in their original relative order. This is what makes the algorithm stable, and stability matters a lot when counting sort is used as a subroutine inside radix sort, where I need to sort by one digit at a time without disturbing the ordering established by previous digit passes.

Mathematical Foundation

If I have n elements and a key range of size k, the total work breaks into three linear passes: counting occurrences takes O(n), computing prefix sums takes O(k), and placing elements into the output takes O(n). So my total time complexity is:

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

The cumulative sum I compute at index i is defined as:

$$C(i) = \sum_{j=0}^{i} count(j)$$

where $count(j)$ is the number of elements in my input equal to value j. This $C(i)$ tells me the correct final index (offset by one, since arrays are zero-indexed) for the last occurrence of value i.

For counting sort to beat comparison-based sorts in practice, I need:

$$k = O(n)$$

If k grows much faster than n, the O(k) term dominates and the algorithm loses its advantage.

Diagrams

flowchart TD
    A[Start: Input array] --> B[Find min and max values]
    B --> C[Build count array of size k+1]
    C --> D[Count occurrences of each value]
    D --> E[Transform counts into cumulative sums]
    E --> F[Traverse input from last to first element]
    F --> G[Place element at position given by cumulative count]
    G --> H[Decrement cumulative count for that value]
    H --> I{More elements?}
    I -->|Yes| F
    I -->|No| J[Output: Sorted array]

sequenceDiagram
    participant Input as Input Array
    participant Count as Count Array
    participant Output as Output Array
    Input->>Count: Tally occurrences of each value
    Count->>Count: Convert to cumulative sums
    Input->>Output: Place elements right-to-left using cumulative index
    Output-->>Output: Sorted result

Pseudocode

COUNTING-SORT(A, k)
    n = length(A)
    let Count[0..k] be a new array, initialized to 0
    let Output[0..n-1] be a new array

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

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

    for i = n-1 down to 0
        Output[Count[A[i]] - 1] = A[i]
        Count[A[i]] = Count[A[i]] - 1

    return Output

Step-by-Step Example

I will sort the array [4, 2, 2, 8, 3, 3, 1], where the values range from 0 to 8, so k = 8.

Step 1 — Count occurrences: Index: 0 1 2 3 4 5 6 7 8 Count: 0 1 2 2 1 0 0 0 1

Step 2 — Cumulative sum: Index: 0 1 2 3 4 5 6 7 8 Count: 0 1 3 5 6 6 6 6 7

Step 3 — Place elements from the end of input:

• A[6] = 1 → Count[1]=1 → place at Output[0], Count[1] becomes 0
• A[5] = 3 → Count[3]=5 → place at Output[4], Count[3] becomes 4
• A[4] = 3 → Count[3]=4 → place at Output[3], Count[3] becomes 3
• A[3] = 8 → Count[8]=7 → place at Output[6], Count[8] becomes 6
• A[2] = 2 → Count[2]=3 → place at Output[2], Count[2] becomes 2
• A[1] = 2 → Count[2]=2 → place at Output[1], Count[2] becomes 1
• A[0] = 4 → Count[4]=6 → place at Output[5], Count[4] becomes 5

Final sorted output: [1, 2, 2, 3, 3, 4, 8]

Time Complexity

• Best case: O(n + k) — counting sort does the same fixed amount of work regardless of the initial arrangement of data.
• Average case: O(n + k) — there is no variability based on input order since the algorithm never compares elements.
• Worst case: O(n + k) — even a reverse-sorted or adversarial input takes exactly the same time.

I consider this predictability one of counting sort’s biggest strengths: its performance is essentially input-order-independent.

Space Complexity

Counting sort needs O(n + k) auxiliary space: O(k) for the count array and O(n) for the output array. This is the trade-off I always weigh — I am spending memory to buy linear time, and if k is very large relative to n, that memory cost can outweigh the speed benefit.

Correctness Analysis

I can convince myself of correctness by looking at the cumulative count array. After the prefix-sum step, $C(i)$ tells me precisely how many elements in the array are less than or equal to value i, which is exactly the count of positions that value i and everything smaller must occupy. Since I decrement the count after placing each element, every occurrence of a repeated value gets a unique, correctly ordered slot, and because I traverse the input in reverse, equal elements retain their original relative order — satisfying stability. Since every element is placed exactly once and its position is derived directly from an accurate count of smaller-or-equal elements, the output array is guaranteed to be sorted.

Advantages

• Runs in linear time O(n + k), beating the O(n log n) barrier of comparison sorts when k is small.
• Stable, which makes it ideal as a subroutine for radix sort.
• Simple to reason about and implement once the range is known.
• Deterministic performance — no worst-case degradation based on input order.

Disadvantages

• Only works on integers or data that can be mapped to integers.
• Becomes inefficient and memory-heavy when the range k is much larger than n.
• Not an in-place algorithm — it requires additional arrays proportional to both n and k.
• Cannot handle negative numbers directly without an offset adjustment.

Applications

I reach for counting sort in situations like:

• Sorting exam scores, ages, or grades where the range of possible values is small and known.
• As the core subroutine inside radix sort, where I sort large numbers digit by digit.
• Bucketing tasks in histogram generation and frequency analysis.
• Sorting characters or strings by ASCII/Unicode value ranges in text-processing pipelines.
• Sorting in graphics and image processing where pixel intensity values are bounded (e.g., 0–255).

Implementation in C

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

// Counting sort for non-negative integers
void countingSort(int arr[], int n) {
    if (n == 0) return;

    // Step 1: find the maximum value to determine range
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }

    // Step 2: create and initialize count array
    int *count = (int *)calloc(max + 1, sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));

    // Step 3: count occurrences of each value
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Step 4: transform counts into cumulative sums
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // Step 5: build output array by placing elements from the end
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

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

    free(count);
    free(output);
}

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

    countingSort(arr, n);

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

    return 0;
}

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

// Counting sort for non-negative integers
void countingSort(int arr[], int n) {
    if (n == 0) return;

    // Step 1: find the maximum value to determine range
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }

    // Step 2: create and initialize count array
    int *count = (int *)calloc(max + 1, sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));

    // Step 3: count occurrences of each value
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Step 4: transform counts into cumulative sums
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // Step 5: build output array by placing elements from the end
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

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

    free(count);
    free(output);
}

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

    countingSort(arr, n);

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

    return 0;
}

Sample Input and Output

Input: [4, 2, 2, 8, 3, 3, 1]

Output: Sorted array: 1 2 2 3 3 4 8

Optimization Techniques

• I only allocate a count array sized to (max – min + 1) rather than (max + 1), which saves memory when the minimum value is far from zero.
• When I need to sort negative numbers, I apply an offset equal to the absolute value of the minimum so every key becomes non-negative before counting.
• For very large ranges, I combine counting sort with radix sort, sorting fixed-width digit groups instead of full values, which keeps k small and predictable.
• I avoid the separate output array when stability is not required, sorting in a more memory-conservative way by directly overwriting positions — though I lose stability in that version.

Common Mistakes

• Forgetting to convert the count array into a cumulative sum before placing elements, which produces an unsorted or incorrect result.
• Iterating the placement step forward instead of backward, which breaks stability even though the final sorted values are still technically correct.
• Not handling negative numbers, causing out-of-bounds array access.
• Assuming counting sort works for floating-point numbers or arbitrary objects without a well-defined integer key.
• Underestimating memory usage when k is very large relative to n, leading to poor performance or memory exhaustion.

Further Reading

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Knuth, Donald E., The Art of Computer Programming, Volume 3: Sorting and Searching: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
• GeeksforGeeks, “Counting Sort”: https://www.geeksforgeeks.org/dsa/counting-sort/
• Visualgo, Sorting Visualizations: https://visualgo.net/en/sorting