Counting Sort: The Sorting Hat's Secret

The Quest Begins (The "Why")

I still remember the first time I got knocked out by a sorting interview question. The interviewer slid a whiteboard marker across the table and said, “You’ve got an array of 10 000 integers, each between 0 and 1 000. Sort it in O(n) time.” My brain went blank. I could picture myself waving a wand, shouting “Sortio!” like a wizard in Harry Potter — except the spell never worked. I fell back on the trusty old quicksort I’d memorized, watched the recursion tree blow up, and felt the sweat start to bead.

That moment stuck with me because it revealed a gap: I knew how to sort, but I didn’t truly grasp why some algorithms could break the n log n barrier. If you’ve ever felt like you’re stuck in a loop of “just use the library sort” and wondered what’s really happening under the hood, you’re in the right place. Let’s grab our metaphorical Sorting Hat and see what it whispers about counting sort.

The Revelation (The Insight)

So why does counting sort work in linear time? The secret isn’t clever recursion or fancy pivoting — it’s direct addressing. Think of the input values as tickets to a concert. If you know the highest possible ticket number (let’s call it k), you can allocate an array of exactly k + 1 seats, one for each possible ticket. Then you simply walk through the crowd, handing each person a seat that matches their ticket number. After everyone’s seated, you read the seats in order and voilà — the crowd is sorted.

Because we never compare two tickets to decide who goes first, we sidestep the comparison‑based lower bound of Ω(n log n). Instead, we trade a bit of extra space (the count array) for a guarantee of O(n + k) time. When k is proportional to n (or at least not astronomically larger), the algorithm collapses to O(n).

That’s the “aha!” moment: if the domain of your data is small and known, you can treat the values themselves as indices. No swapping, no partitioning — just counting.

Wielding the Power (Code & Examples)

Let’s see the spell in action. Below is a straightforward Python implementation that sorts an array of non‑negative integers where the maximum value is known (max_val).

def counting_sort(arr, max_val):
    """
    Sorts arr in O(n + max_val) time.
    Assumes all elements are in the range [0, max_val].
    """
    # Step 1: create the count array
    count = [0] * (max_val + 1)

    # Step 2: tally occurrences
    for num in arr:
        count[num] += 1

    # Step 3: reconstruct the sorted array
    sorted_arr = []
    for num, freq in enumerate(count):
        sorted_arr.extend([num] * freq)

    return sorted_arr

Why this is faster than the naïve approach

If you tried to sort the same data with insertion sort (O(n²)) or even quicksort (average O(n log n)), you’d spend time shuffling elements around. Counting sort merely increments counters and then walks the count array once — two linear passes plus a tiny overhead for building the output.

Common traps (the “traps” on the quest)

1. Assuming the range is tiny when it isn’t – If max_val is, say, 1 000 000 while n is only 100, you’ll allocate a million‑slot array, wasting memory and defeating the purpose. Always check that max_val is reasonable relative to n.
2. Forgetting stability – The version above is stable because we output numbers in increasing order and preserve the original order of equal keys via extend. If you instead built the output by iterating backwards through the original array (as some textbooks do), you must be careful to maintain stability if it matters for your use case.

Real‑world interview problems

Problem 1 – “Sort Colors” (LeetCode 75)

Prompt: Given an array nums containing only 0, 1, and 2, sort them in‑place so that all 0s come first, then 1s, then 2s.

Solution: This is counting sort with max_val = 2. We allocate a size‑3 count array, tally, then overwrite nums in order. Runs in O(n) time, O(1) extra space (since the count array is constant size).

Problem 2 – “Sort Student Scores”

Prompt: You have an array of exam scores, each an integer between 0 and 100 inclusive. Return the scores sorted from lowest to highest.

Solution: Apply counting sort with max_val = 100. The algorithm touches each score once to count, then walks 101 buckets to rebuild the list — linear in the number of students, independent of the distribution of scores.

Both problems appear regularly in technical interviews because they test whether you recognize when the input’s bounded domain unlocks a linear‑time solution.

Why This New Power Matters

Armed with counting sort, you can now tackle a whole class of problems that once felt like they needed heavyweight comparison‑based sorters. Think of radix sort (which builds on counting sort to sort multi‑digit numbers), or any scenario where you’re dealing with limited‑range keys — grades, ages, timestamps discretized to seconds, or even categorical data encoded as integers.

Beyond interviews, this mindset shift — look for structure in the data before choosing an algorithm — makes you a more effective engineer. You’ll start spotting opportunities to replace O(n log n) libraries with O(n) passes, shaving off precious milliseconds in high‑frequency trading systems, game leaderboards, or real‑time analytics pipelines.

And the best part? The code is short, easy to reason about, and has virtually no hidden bugs once you respect the range constraint. It’s the kind of algorithm that feels like a cheat code — until you realize it’s just clever use of the facts you already have.

Your Turn

Here’s a little challenge to cement the spell:

Take an array of integers where each value is between 0 and 10 000. Write a function that returns the **k‑th smallest* element in O(n) time using only O(max_val) extra space (you may reuse the counting‑sort idea). Post your solution in the comments or tweet it with #CountingSortQuest — let’s see who can optimize it the fastest!*

Go forth, dear developer, and may your sorts always be linear and your bugs few. Happy coding! 🚀