What Is Counting Sort? The O(n) Sort That Skips Every Comparison

Every sort you've ever written compares elements. Quicksort compares. Mergesort compares. Your bubble sort from freshman year definitely compared, in nested for-loops you'd rather forget. They all ask the same question, millions of times: is A bigger than B?

Counting sort never asks. It doesn't care which element is bigger. It counts how many times each value appears, then reconstructs the sorted array from those counts. No comparisons. No swaps. Just arithmetic.

That's why it can sort in O(n + k) time, where k is the range of values, breaking through the O(n log n) floor that traps every comparison sort. Knowing when to reach for it in a coding interview is exactly what separates a hire from a strong hire.

Why Every Comparison Sort Is Trapped at O(n log n)

Every comparison-based sort must take at least O(n log n) time in the worst case. This isn't a failure of imagination. It's a proof.

Here's the sketch: sorting n elements means navigating a binary decision tree where each node asks "is A > B?" The tree has n! possible leaf nodes (one per permutation), so its height is at least log₂(n!). By Stirling's approximation, log₂(n!) ≈ n log n. No matter how clever you get about which comparisons to make, you cannot shrink this tree. No comparison sort escapes it.

Counting sort sidesteps this completely because it never asks which element is bigger. It just asks: "how many times does each value appear?" That's a completely different operation, and it breaks out of the comparison sort lower bound entirely.

How Counting Sort Actually Works

You have an array of integers with values in some known, bounded range. You count how many times each value appears. Then you walk through the counts and write each value back the right number of times.

That's it. No comparisons, no pivots, no merges.

Here's the intuition. Imagine sorting a classroom of students by age, and you know every age is between 18 and 25. You don't need to compare students. You just count: "3 students are 18, 1 is 19, 4 are 20..." Then you write them out in order. You've sorted n students in O(n + k) time where k = 8 (the range 18..25).

Walk Through the Array Once

Take this array: [4, 2, 2, 8, 3, 3, 1]

Step 1: Find the range.

min = 1, max = 8, so we need a count array of size 8.

Step 2: Count each value.

Walk through the input and increment count[value - min] for each element:

value:  1  2  3  4  5  6  7  8
count:  1  2  2  1  0  0  0  1

The value 2 appears twice, so count[1] (index = 2 - 1) is 2. The value 5 never appears, so count[4] is 0.

Step 3: Reconstruct the sorted array.

Walk through the count array left to right. For each index i, emit the value i + min exactly count[i] times:

i=0: emit 1 once     → [1]
i=1: emit 2 twice    → [1, 2, 2]
i=2: emit 3 twice    → [1, 2, 2, 3, 3]
i=3: emit 4 once     → [1, 2, 2, 3, 3, 4]
i=4: emit 5 zero     → (nothing)
...
i=7: emit 8 once     → [1, 2, 2, 3, 3, 4, 8]

Done. Sorted in two passes over the data plus one pass over the count array.

O(n + k): Where the Time Actually Goes

Time: O(n + k)

First pass (building count array): O(n)
Second pass (reconstructing output): O(n + k), because you walk the count array once (O(k)) and write n elements total (O(n))

When k = O(n), this collapses to O(n). That's linear time sorting. When k >> n (sparse integers across a huge range), the k term dominates and counting sort becomes slow or memory-prohibitive.

Space: O(k)

The count array takes O(k) space regardless of n. If your values are 32-bit integers with no bounds, k = 2³² and you need 4 GB of count array. That's the moment you close the counting sort tab and pretend this conversation never happened.

For a deeper look at how complexity analysis works across different approaches, see what time complexity really measures.

Stability, and Why Radix Sort Cares

The simple reconstruction above is not stable. If two elements have the same value, their original order is lost. You're emitting repeated values from a count, not tracking which original element was which.

For use cases where stability matters (notably as a subroutine inside radix sort), you need the prefix-sum variant. Here's how it works:

After building the count array, compute a prefix sum (cumulative counts):

Before: [1, 2, 2, 1, 0, 0, 0, 1]
After:  [1, 3, 5, 6, 6, 6, 6, 7]

Each entry now tells you: "the last occurrence of this value belongs at index count[v] - 1." Then you iterate through the input right to left, placing each element at position --count[value - min] in the output array. Because you go right to left and decrement, equal elements land in their original relative order.

This stable variant is what makes radix sort work: it sorts by each digit using a stable counting sort, and stability ensures earlier digit passes aren't scrambled by later ones. The stable sort deep-dive covers why stability matters beyond just counting sort.

When Counting Sort Wins

Use counting sort when:

Values are bounded integers in a known, reasonably small range
k is proportional to n (otherwise the k term dominates)
You need linear time and the constraints allow it
Stability is required (with the prefix-sum variant)
Values are non-negative (or you can shift them to be with a min-offset)

Avoid counting sort when:

Values are floating-point numbers (no discrete index)
Values are unbounded or sparse across a huge range
You're sorting objects by a key that isn't a small integer
Memory is tight and k >> n

The counting sort vs radix sort comparison breaks down how these constraints interact when you're sorting multi-digit numbers.

Why This Matters in Your Next Interview

Interviewers test counting sort in a few specific ways.

The "can you beat O(n log n)?" question. If the problem says "sort n integers where every value is between 0 and k," the expected answer is counting sort (or radix sort). Using quicksort here is technically correct. It also misses the point entirely, and the interviewer knows it.

The constraints are the hint. When a problem gives you a small range of integer values (ages, grades, characters), that's not flavor text. The constraint exists so you can use a non-comparison sort. The interviewer put it there deliberately. Ignoring it and reaching for arr.sort() out of reflex is exactly the kind of thing that turns into "candidate missed the key insight" in the write-up.

Character frequency problems. Many string problems (anagram checks, character counts, frequency analysis) are secretly counting sort: build a frequency array of size 26 (for lowercase ASCII), and the problem reduces to array comparison. You're not sorting, but you're using the same underlying idea.

Radix sort subroutine. If you're asked to implement radix sort, you'll need counting sort. The two algorithms are inseparable.

The common mistake is defaulting to arr.sort() when the constraints explicitly enable O(n). Reaching for counting sort when the range is bounded is exactly what separates a hire from a strong hire.

If you want to practice spotting these constraint-driven optimizations under pressure, SpaceComplexity runs voice-based mock interviews where you have to explain your reasoning in real time, not just produce working code.

One Structure, Every Language

These implementations use the simple (non-stable) variant with a min-offset to handle negative integers correctly.

Python 3

def counting_sort(arr: list[int]) -> list[int]:
    if not arr:
        return []
    min_val, max_val = min(arr), max(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    result = []
    for i, c in enumerate(count):
        result.extend([i + min_val] * c)
    return result

Python 2

def counting_sort(arr):
    if not arr:
        return []
    min_val, max_val = min(arr), max(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    result = []
    for i, c in enumerate(count):
        result.extend([i + min_val] * c)
    return result

JavaScript

function countingSort(arr) {
    if (arr.length === 0) return [];
    const minVal = Math.min(...arr);
    const maxVal = Math.max(...arr);
    const count = new Array(maxVal - minVal + 1).fill(0);
    for (const num of arr) {
        count[num - minVal]++;
    }
    const result = [];
    for (let i = 0; i < count.length; i++) {
        for (let j = 0; j < count[i]; j++) {
            result.push(i + minVal);
        }
    }
    return result;
}

TypeScript

function countingSort(arr: number[]): number[] {
    if (arr.length === 0) return [];
    const minVal = Math.min(...arr);
    const maxVal = Math.max(...arr);
    const count = new Array<number>(maxVal - minVal + 1).fill(0);
    for (const num of arr) {
        count[num - minVal]++;
    }
    const result: number[] = [];
    for (let i = 0; i < count.length; i++) {
        for (let j = 0; j < count[i]; j++) {
            result.push(i + minVal);
        }
    }
    return result;
}

Java

public static int[] countingSort(int[] arr) {
    if (arr.length == 0) return arr;
    int minVal = Arrays.stream(arr).min().getAsInt();
    int maxVal = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[maxVal - minVal + 1];
    for (int num : arr) {
        count[num - minVal]++;
    }
    int[] result = new int[arr.length];
    int idx = 0;
    for (int i = 0; i < count.length; i++) {
        for (int j = 0; j < count[i]; j++) {
            result[idx++] = i + minVal;
        }
    }
    return result;
}

C++

#include <algorithm>
#include <vector>

std::vector<int> countingSort(std::vector<int> arr) {
    if (arr.empty()) return {};
    int minVal = *std::min_element(arr.begin(), arr.end());
    int maxVal = *std::max_element(arr.begin(), arr.end());
    std::vector<int> count(maxVal - minVal + 1, 0);
    for (int num : arr) {
        count[num - minVal]++;
    }
    std::vector<int> result;
    result.reserve(arr.size());
    for (int i = 0; i < static_cast<int>(count.size()); i++) {
        for (int j = 0; j < count[i]; j++) {
            result.push_back(i + minVal);
        }
    }
    return result;
}

#include <stdlib.h>
#include <string.h>

void countingSort(int *arr, int n) {
    if (n == 0) return;
    int minVal = arr[0], maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < minVal) minVal = arr[i];
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    int range = maxVal - minVal + 1;
    int *count = (int *)calloc(range, sizeof(int));
    for (int i = 0; i < n; i++) {
        count[arr[i] - minVal]++;
    }
    int idx = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]-- > 0) {
            arr[idx++] = i + minVal;
        }
    }
    free(count);
}

func countingSort(arr []int) []int {
    if len(arr) == 0 {
        return []int{}
    }
    minVal, maxVal := arr[0], arr[0]
    for _, num := range arr {
        if num < minVal {
            minVal = num
        }
        if num > maxVal {
            maxVal = num
        }
    }
    count := make([]int, maxVal-minVal+1)
    for _, num := range arr {
        count[num-minVal]++
    }
    result := make([]int, 0, len(arr))
    for i, c := range count {
        for j := 0; j < c; j++ {
            result = append(result, i+minVal)
        }
    }
    return result
}

Rust

fn counting_sort(arr: &mut Vec<i32>) {
    if arr.is_empty() {
        return;
    }
    let min_val = *arr.iter().min().unwrap();
    let max_val = *arr.iter().max().unwrap();
    let range = (max_val - min_val + 1) as usize;
    let mut count = vec![0usize; range];
    for &num in arr.iter() {
        count[(num - min_val) as usize] += 1;
    }
    let mut idx = 0;
    for (i, &c) in count.iter().enumerate() {
        for _ in 0..c {
            arr[idx] = i as i32 + min_val;
            idx += 1;
        }
    }
}

Swift

func countingSort(_ arr: [Int]) -> [Int] {
    guard !arr.isEmpty else { return [] }
    let minVal = arr.min()!
    let maxVal = arr.max()!
    var count = Array(repeating: 0, count: maxVal - minVal + 1)
    for num in arr {
        count[num - minVal] += 1
    }
    var result: [Int] = []
    result.reserveCapacity(arr.count)
    for (i, c) in count.enumerated() {
        result.append(contentsOf: Array(repeating: i + minVal, count: c))
    }
    return result
}

Kotlin

fun countingSort(arr: IntArray): IntArray {
    if (arr.isEmpty()) return intArrayOf()
    val minVal = arr.minOrNull()!!
    val maxVal = arr.maxOrNull()!!
    val count = IntArray(maxVal - minVal + 1)
    for (num in arr) {
        count[num - minVal]++
    }
    val result = mutableListOf<Int>()
    for ((i, c) in count.withIndex()) {
        repeat(c) { result.add(i + minVal) }
    }
    return result.toIntArray()
}

public static int[] CountingSort(int[] arr) {
    if (arr.Length == 0) return arr;
    int minVal = arr.Min();
    int maxVal = arr.Max();
    int[] count = new int[maxVal - minVal + 1];
    foreach (int num in arr) {
        count[num - minVal]++;
    }
    List<int> result = new List<int>(arr.Length);
    for (int i = 0; i < count.Length; i++) {
        for (int j = 0; j < count[i]; j++) {
            result.Add(i + minVal);
        }
    }
    return result.ToArray();
}

Ruby

def counting_sort(arr)
    return [] if arr.empty?
    min_val = arr.min
    max_val = arr.max
    count = Array.new(max_val - min_val + 1, 0)
    arr.each { |num| count[num - min_val] += 1 }
    result = []
    count.each_with_index { |c, i| c.times { result << i + min_val } }
    result
end

PHP

function countingSort(array $arr): array {
    if (empty($arr)) return [];
    $minVal = min($arr);
    $maxVal = max($arr);
    $count = array_fill(0, $maxVal - $minVal + 1, 0);
    foreach ($arr as $num) {
        $count[$num - $minVal]++;
    }
    $result = [];
    foreach ($count as $i => $c) {
        for ($j = 0; $j < $c; $j++) {
            $result[] = $i + $minVal;
        }
    }
    return $result;
}

What to Take Into Your Interview

The constraint "values are between 0 and k" is a direct hint toward counting sort. When you see a bounded integer range, the expected answer is not quicksort.
The simple variant is not stable. The prefix-sum variant is stable and required for correct radix sort behavior.
Character frequency arrays in string problems (anagram checks, frequency analysis) use the exact same idea with k = 26.
When k >> n, the O(k) space and time costs dominate. A 32-bit integer range needs 4 GB of count array. That's when you stop.