If you've spent any time on Codeforces, you've probably had this thought at least once:

"Sorting is such a basic operation. Why is O(n log n) the best we can do? Can't someone just be clever enough to sort in O(n)?"

The honest answer is: it depends on what kind of sorting you're doing. For general-purpose comparison-based sorting, O(n log n) isn't just "the best algorithm found so far" — it's a provable mathematical floor. No algorithm, however clever, can beat it. But for special cases, O(n) sorting is not only possible, it's a well-known trick that shows up constantly in competitive programming.

This post explains both halves of that story.

1. The Claim Needs to Be Precise

"You can't sort in O(n)" is only true for a specific class of algorithms: comparison-based sorts. These are algorithms that determine the final order of elements purely by comparing pairs of elements — if a[i] < a[j]), and nothing else. No looking at the actual values, no hashing, no using them as array indices.

Merge sort, quicksort, heapsort, insertion sort — all comparison-based. All bounded below by Ω(n log n) comparisons in the worst case.

The moment you allow yourself to use the actual values of the elements (not just compare them), the rules change completely — more on that in Section 3.

1. The Decision Tree Argument (Why the Bound Is Real)

This is the elegant part, and it's worth understanding fully rather than just memorizing.

Setup: Any comparison-based sorting algorithm can be modeled as a binary decision tree.

Each internal node represents one comparison, like a[i] < a[j]. Depending on the outcome (true/false), the algorithm branches left or right. Each leaf of the tree corresponds to one final, fully-determined ordering of the input.

Key fact: For n distinct elements, there are n! possible orderings. Since the algorithm must be able to produce any of these orderings depending on the input, the decision tree must have at least n! leaves.

Height vs. leaves: A binary tree of height h can have at most 2^h leaves. So we need:

2^h ≥ n! h ≥ log2(n!)

Using Stirling's approximation:

log2(n!) = Θ(n log n)

So the height of the tree — which represents the worst-case number of comparisons — must be at least Ω(n log n). Since every comparison takes at least constant time, any comparison-based sort needs Ω(n log n) time in the worst case.

This is an information-theoretic argument, not an engineering limitation. It's not "we haven't found a faster algorithm yet" — it's a hard mathematical ceiling on how much information a sequence of yes/no comparisons can extract. Merge sort and heapsort, at O(n log n), are actually asymptotically optimal.

1. So How Do Counting Sort, Radix Sort, and Bucket Sort Hit O(n)?

They don't break the lower bound — they step outside the model the bound applies to. They don't compare elements at all.

Counting Sort — O(n + k)

Assumes elements are integers in a small known range [0, k). Instead of comparing, it counts occurrences of each value directly and uses those counts to place elements — essentially using the value itself as an array index.

cppvoid countingSort(vector& a, int maxVal) { vector count(maxVal + 1, 0); for (int x : a) count[x]++; int idx = 0; for (int v = 0; v <= maxVal; v++) while (count[v]--) a[idx++] = v; }

Works great when k = O(n). Falls apart if k is huge (say, values up to 10^9) — then it's not O(n) anymore, it's O(n + k).

Radix Sort — O(d · (n + k))

Sorts numbers digit by digit (or byte by byte), using counting sort as a stable subroutine for each digit position. For d digits, this gives O(d(n+k)) — linear when d is a small constant (e.g., fixed 32-bit or 64-bit integers).

Bucket Sort — O(n) expected

Assumes input is roughly uniformly distributed over a range. Distributes elements into n buckets, sorts each small bucket individually (often with insertion sort), then concatenates. Works well in expectation when the distribution assumption holds; degrades to O(n log n) or worse if it doesn't.

The common thread: all three exploit extra structure in the input — a bounded range, a fixed number of digits, a known distribution — that comparison sort doesn't get to assume. They're solving an easier problem than "sort arbitrary comparable elements," so the Ω(n log n) bound simply doesn't apply to them.

1. The Competitive Programming Angle

Here's the pattern worth internalizing: if you ever submit an O(n) or O(n + k) sort on Codeforces and it passes, it's never because you found a magical general-purpose linear sort. Look at the constraints — you'll almost always find one of these:

Values are bounded by a small range (a[i] ≤ 10^6) → counting sort Values are integers with bounded digit count → radix sort You're sorting into a fixed number of buckets/categories → bucket sort or even just direct placement

A concrete example: if a problem guarantees 1 ≤ a[i] ≤ 2·10^5 and n ≤ 2·10^5, counting sort in O(n + max_val) is often faster in practice than std::sort's O(n log n) — and it's a nice trick to have ready when TLE is close.

1. Takeaway

Ω(n log n) is a provable lower bound for comparison-based sorting — not a limitation of current algorithms, but a mathematical fact about how much information comparisons can extract. Merge sort / heapsort achieve this bound, so they're optimal within their model. Linear-time sorts (counting, radix, bucket) escape the bound by not comparing — they use the actual values of elements, exploiting extra assumptions about the input. On Codeforces, spotting when a problem's constraints quietly permit an O(n) sort is a genuinely useful skill, not just trivia.

Next time you see "why can't we just sort in O(n)?" in a comment section, you'll know the real answer: you can — just not by comparing.