Counting Sort

Most sorting you have seen so far works by comparing two values and asking “which one is bigger?” Think of bubble sort, merge sort, or quick sort. Every one of them works by comparing. The problem is that comparing has a speed limit. No matter how clever you are, comparison sorts cannot go faster than O(n log n). So here is the question. What if we never compare at all? Counting sort does exactly that. It just counts. And that lets it sort faster than the comparison limit when the numbers are small.

🎯 The Problem First

Say you have a list of student marks, all between 0 and 100. Thousands of students. You want them sorted.

A comparison sort will keep asking “is 85 bigger than 72?” over and over. That work piles up.

But the marks are just numbers from 0 to 100. There are only 101 possible values. So instead of comparing marks against each other, you can count how many students got each mark. That counting idea is the whole trick behind counting sort, a sorting method that puts things in order by counting how often each value appears instead of comparing values.

🧠 The Idea With a Real Example

Imagine a teacher collecting quiz scores. The scores can only be 0, 1, 2, 3, 4, or 5.

The teacher does not line up papers and compare them. She just makes a tally. Five students got a 2, three students got a 4, and so on. Then she reads the tally back in order. All the 0s first, then the 1s, then the 2s. The papers come out sorted.

That tally is the count array, a small array where each index stands for a possible value and stores how many times that value appeared.

Let us sort this list: [2, 5, 3, 0, 2, 3, 0, 3]. The values go from 0 to 5.

First we count each value.

See the count array [2, 0, 2, 3, 0, 1]? It reads like this:

• value 0 appeared 2 times
• value 1 appeared 0 times
• value 2 appeared 2 times
• value 3 appeared 3 times
• value 4 appeared 0 times
• value 5 appeared 1 time

Now the rebuild step. We walk the count array from the smallest value to the largest. For each value, we write it out as many times as the count says. So we write two 0s, skip 1, write two 2s, write three 3s, skip 4, and write one 5. That gives [0, 0, 2, 2, 3, 3, 3, 5]. The list is fully sorted, and we never compared two numbers even once.

🪜 Steps to Do Counting Sort

Here is the plan before we write any code.

1. Find the largest value in the input. Call it max. This tells us how big the count array must be.
2. Make a count array of size max + 1, filled with zeros. The + 1 is because we need a slot for 0 too.
3. Walk through the input. For every value v, do count[v] = count[v] + 1. Now each slot holds how many times that value appeared.
4. Rebuild the sorted list. Walk the count array from index 0 upward. For each index i, write the value i into the output count[i] times.
5. The output is now sorted.

💻 Counting Sort in Code

Below is a clean counting sort. We write a function that takes the array, counts the values, then rebuilds the array in sorted order. The same array is filled back in place.

#include <stdio.h>

// Sort an array of small non-negative integers by counting.
void countingSort(int arr[], int n) {
    // Step 1: find the largest value.
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }

    // Step 2: count array of size max + 1, all zeros.
    int count[max + 1];
    for (int i = 0; i <= max; i++) count[i] = 0;

    // Step 3: count how many times each value appears.
    for (int i = 0; i < n; i++) count[arr[i]]++;

    // Step 4: rebuild the array in sorted order.
    int pos = 0;
    for (int v = 0; v <= max; v++) {
        while (count[v] > 0) {
            arr[pos] = v;
            pos++;
            count[v]--;
        }
    }
}

int main() {
    int arr[] = {2, 5, 3, 0, 2, 3, 0, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    countingSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

0 0 2 2 3 3 3 5

#include <iostream>
#include <vector>
using namespace std;

// Sort a vector of small non-negative integers by counting.
void countingSort(vector<int>& arr) {
    int n = arr.size();

    // Step 1: find the largest value.
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }

    // Step 2: count array of size maxVal + 1, all zeros.
    vector<int> count(maxVal + 1, 0);

    // Step 3: count how many times each value appears.
    for (int i = 0; i < n; i++) count[arr[i]]++;

    // Step 4: rebuild the array in sorted order.
    int pos = 0;
    for (int v = 0; v <= maxVal; v++) {
        while (count[v] > 0) {
            arr[pos++] = v;
            count[v]--;
        }
    }
}

int main() {
    vector<int> arr = {2, 5, 3, 0, 2, 3, 0, 3};
    countingSort(arr);
    for (int x : arr) cout << x << " ";
    cout << endl;
    return 0;
}

0 0 2 2 3 3 3 5

public class CountingSort {

    // Sort an array of small non-negative integers by counting.
    static void countingSort(int[] arr) {
        int n = arr.length;

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

        // Step 2: count array of size max + 1, all zeros.
        int[] count = new int[max + 1];

        // Step 3: count how many times each value appears.
        for (int i = 0; i < n; i++) count[arr[i]]++;

        // Step 4: rebuild the array in sorted order.
        int pos = 0;
        for (int v = 0; v <= max; v++) {
            while (count[v] > 0) {
                arr[pos++] = v;
                count[v]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 0, 2, 3, 0, 3};
        countingSort(arr);
        for (int x : arr) System.out.print(x + " ");
        System.out.println();
    }
}

0 0 2 2 3 3 3 5

# Sort a list of small non-negative integers by counting.
def counting_sort(arr):
    # Step 1: find the largest value.
    max_val = max(arr)

    # Step 2: count array of size max_val + 1, all zeros.
    count = [0] * (max_val + 1)

    # Step 3: count how many times each value appears.
    for v in arr:
        count[v] += 1

    # Step 4: rebuild the list in sorted order.
    pos = 0
    for value in range(max_val + 1):
        while count[value] > 0:
            arr[pos] = value
            pos += 1
            count[value] -= 1
    return arr


numbers = [2, 5, 3, 0, 2, 3, 0, 3]
print(counting_sort(numbers))

[0, 0, 2, 2, 3, 3, 3, 5]

// Sort an array of small non-negative integers by counting.
function countingSort(arr) {
  // Step 1: find the largest value.
  const max = Math.max(...arr);

  // Step 2: count array of size max + 1, all zeros.
  const count = new Array(max + 1).fill(0);

  // Step 3: count how many times each value appears.
  for (const v of arr) count[v]++;

  // Step 4: rebuild the array in sorted order.
  let pos = 0;
  for (let value = 0; value <= max; value++) {
    while (count[value] > 0) {
      arr[pos++] = value;
      count[value]--;
    }
  }
  return arr;
}

const numbers = [2, 5, 3, 0, 2, 3, 0, 3];
console.log(countingSort(numbers).join(" "));

0 0 2 2 3 3 3 5

⏱️ How Fast Is It?

Let n be how many items you are sorting. Let k be the size of the value range, which is max + 1.

We do two walks. One walk over the n input items to count them. One walk over the k count slots to rebuild. So the total work is the two walks added together.

This is the special part. Counting sort is non-comparison, meaning it never asks “is a bigger than b?” Because it skips comparing, it is not bound by the O(n log n) speed limit that applies to every comparison sort. For small-range integers, it just walks past that barrier.

But watch the k. Say you try to sort the values [1, 1000000]. Now k is a million even though n is only 2. The count array would have a million slots for two numbers. That is wasteful and slow. So big ranges kill counting sort.

Here is the full picture.

Notice the time is the same in every case. Counting sort does not care if the input is already sorted or fully shuffled. It always does the same two walks.

⚠️ Common Mistakes

A few things trip people up. Watch out for these.

• Making the count array size max instead of max + 1. You need a slot for the value max itself, so the size must be max + 1. Off by one here crashes the program.
• Forgetting that plain counting sort assumes non-negative integers. If your data has negative numbers, you must shift every value by the minimum first, or the index goes negative.
• Using it on a huge range. If values go up to a million but you only have ten items, the count array wastes a million slots. Pick a different sort then.
• Trying to sort decimals or text with it. The value has to be a whole number you can use as an array index. Counting sort cannot index by 3.5 or by “apple”.

🧩 What You’ve Learned

• ✅ Counting sort sorts by counting how often each value appears, not by comparing values.
• ✅ The count array has one slot per possible value, and each slot holds that value’s frequency.
• ✅ The rebuild step walks the count array and writes each value as many times as it was counted.
• ✅ It runs in O(n + k) time and O(n + k) space, where k is the size of the value range.
• ✅ Because it never compares, it beats the O(n log n) limit for small-range integers, but a large range makes it slow and wasteful.

🚀 What’s Next?

• Radix Sort
• Sorting Algorithms Comparison