Can Sorting Get Any More Efficient?

Back when I first started learning DSA, sorting was introduced to me as one of the most basic concepts. I don’t know about you, but it was also the first time I ever heard about something called time complexity. And from there, the rabbit hole begins.

We start with Bubble Sort, then Insertion Sort, then Merge Sort, then Quick Sort, and so on. The list is long — and half of those algorithms exist more as intellectual exercises than practical improvements. But the theme is always the same:
make sorting more efficient.

Eventually, though, we hit the wall:
O(n log n) for comparison-based sorting.
Most people accept it as a kind of “sorting demigod” — an immovable limit.
But my brain never stopped asking: can we do a little better somewhere?

And today I had something like a mini-revelation.

No, I didn’t break the O(n log n) lower bound.
But I did find a very small, very simple idea that keeps the time complexity bounded between O(n) and O(n log n) — and in practice, often much closer to linear time.

The idea (almost embarrassingly simple)

Instead of sorting the full array, what if we:

1. Extract all unique values

2. Count how many times each value occurs

3. Sort only the m unique elements, not the full n sized array

Reconstruct the array by expanding each sorted unique value according to its count

That’s it.
Unrealistically simple.

This gives us:

Time complexity = O(n + m log m)
where m = number of unique values.

Worst case, m = n, and you get normal O(n log n).
Best/random case, m can be much smaller — and performance becomes closer to linear.

We use an unordered_map (hash map), because counting unique elements is pretty much its natural habitat.

void boxsort(vector<int>& array) {

    unordered_map<int, size_t> boxmap;

    for (size_t i = 0; i < array.size(); i++) {
        boxmap[array[i]]++;
    }

    vector<int> unique;

    for (auto it : boxmap) {
        unique.push_back(it.first);
    }

    sort(unique.begin(), unique.end());

    for(size_t i = 0, mrk = 0; i < unique.size(); i++) {

        for (size_t j = 0; j < boxmap[unique[i]]; j++) {
            array[mrk++] = unique[i];
        }
    }

}