1. The problem
You have written several sorts by now. Bubble sort, selection sort and insertion sort take O(n2). Merge sort and quicksort take O(n log n), quicksort on average. For a whole family of sorts, a sort that runs in O(n) on any list is impossible, and there is an exact reason. Every sort you have seen learns about the order in one way. It compares two elements, asks "is this one smaller?", and decides what to do next from the "yes" or "no". It has no other information about the order. This lesson shows why that limits the speed and computes the limit.
This code won't go into production. You need it to see when to stop speeding up a comparison sort and use a different kind of sort instead.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- keys are integers in a small known range
- sort ages, grades, or bounded counts
- need O(n) and comparisons are the bottleneck
- sort by digit or fixed-width key
- n large but the value range is much smaller than n
Looks similar, isn't
- Fast sort (merge / quick)
No comparison sort can beat n log n. Reading the key steps around that limit entirely.
- Hash set / map
A map counts values too, but it keeps no order. Counting sort uses the value as an index.
- Sort with a custom comparator
A comparator describes the order between two items. Counting sort never looks at two items.
- Elementary sorts (selection, bubble, insertion)
Those compare neighbours and cost n squared. Counting sort is linear when the range allows it.
n values with keys under k gives O(n + k). Radix sort costs O(d times n) across d digits.
On LeetCode
No LeetCode problem asks you to prove this limit. It tells you when to stop looking for a faster comparison sort, and a problem that demands O(n) time on numbers, like Maximum Gap, needs the counting or radix sort from lessons 39 and 40.