Step 4 of 6

Counting sort

Comparison sorts, which only learn about the data by asking "is a < b?", can't beat O(n log n) in the worst case. That's a proven limit. But when the values are small integers in a known range 0..k, you don't need comparisons at all: count how many times each value occurs, then write the values back in order. That's O(n + k).

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<int> grades = {3, 1, 4, 1, 5, 3, 3, 0, 5};    // grades 0..5
    std::vector<int> count(6, 0);
    for (int g : grades) count[g]++;                        // tally

    for (int g = 0; g <= 5; g++) {
        std::cout << g << ": " << std::string(count[g], '#') << "\n";
    }

    std::size_t k = 0;
    for (int g = 0; g <= 5; g++) {
        for (int c = 0; c < count[g]; c++) grades[k++] = g;   // write back in order
    }
    for (int g : grades) std::cout << g << " ";
    std::cout << "\n";
}

0: #
1: ##
2: 
3: ###
4: #
5: ##
0 1 1 3 3 3 4 5 5 

How it works

• The count array has one slot per possible value: max_value + 1 slots, because the range includes both 0 and the maximum.
• The first pass tallies; the second writes each value back as many times as it was counted.
• No element is ever compared with another.

When to use it

It shines when the range k is small compared with n: ages, exam scores, bytes (0 to 255), days of the month. Sorting a million ages is basically instant. It's also the building block of radix sort, which sorts big numbers digit by digit with counting passes. If k is huge (say, arbitrary 32-bit ints), the count array would be enormous, and a comparison sort is the better choice.

Your turn: write void counting_sort(std::vector<int>& v, int max_value) for values in 0..max_value.

Previous: Quicksort and partitioning Next: Stability and custom comparators