Counting Sort and Choosing a Sort

Sorting without comparing

When values are small whole numbers (like marks 0–100), just count each value and write them out in order:

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

int main() {
    vector<int> marks = {7, 3, 9, 3, 0, 7, 7, 10};
    vector<int> count(11, 0);
    for (int m : marks) count[m]++;
    for (int value = 0; value <= 10; value++)
        for (int k = 0; k < count[value]; k++) cout << value << ' ';
    cout << endl;
    return 0;
}

Output

0 3 3 7 7 7 9 10 

Think of it like this: Sorting coins into ₹1, ₹2, ₹5 and ₹10 piles, then stacking the piles in order. No coin is compared to another.

O(n + k), where k is the range of values – faster than O(n log n) when k is small.

Remember: No comparison-based sort can beat O(n log n) in general; counting sort is faster only because it doesn't compare.