Sorting: why O(n log n) beats O(n²)
Sorting is the standard place to meet the difference between O(n²) and O(n log n), because you can watch both happen to the same array and count what each one costs.
Below, 14 values starting in the same order every time. Bubble sort settles them in 91 comparisons. Merge sort settles the same 14 values in 31. Nothing is estimated: each comparison is counted as it happens.
Watch bubble first, and notice how much of its work is moving a value one place at a time. Then merge, which never compares most pairs at all, because it only ever merges runs that are already in order.
1function bubble(a) {2 for (let end = a.length - 1; end > 0; end--) {3 for (let i = 0; i < end; i++) {4 if (a[i] > a[i + 1]) swap(a, i, i + 1)5 }6 }7}
The array
orange is being compared, teal is settled
bubble sort · O(n²)
- 1
- 3
- 5
- 7
- 9
- 10
- 8
- 6
- 4
- 2
0 comparisons · 0 swaps
10 values, in no particular order, and bubble sort is about to put them straight. Watch the comparison count more than the array.
Why the quadratic sorts are quadratic, and what merge sort does instead.
Why the quadratic sorts are quadratic
Bubble sort makes a pass, comparing every neighbouring pair, and after each pass the largest remaining value has reached the end. That is one value placed per pass, and a pass costs as many comparisons as there are items left.
So the work is n plus n minus one plus n minus two, all the way down, which is about n²/2. At 14 items that is exactly 91 comparisons, and the animation counts every one of them.
Insertion sort looks different and costs the same in the worst case. It takes each value and walks it backwards into place, which is again a pass per item. Its advantage is elsewhere, and worth knowing: on input that is already nearly sorted, each value walks almost nowhere and the whole thing behaves linearly.
What merge sort does instead
Merge sort never compares most pairs. It sorts runs of one, which are sorted by definition, then merges neighbouring runs into longer sorted runs, then merges those. Each round doubles the run length, so the number of rounds is the number of times the array can be halved.
Merging two sorted runs is the cheap part. Because both sides are already in order, you only ever compare their two front values, take the smaller, and move on. Every item is looked at once per round.
One pass over everything, log n times. That product is the shape, and the reason it beats a quadratic sort by more and more as the array grows rather than by a constant amount.
The counts, at the same size
On 14 items: 91 comparisons for bubble sort, 55 for insertion sort, 31 for merge sort. Drag the slider and watch the first two climb far faster than the third.
n log n is a floor, not a target
No sort that works by comparing pairs can beat n log n in the worst case, and the proof is a counting argument rather than a fact about any particular algorithm. There are n! possible orderings, each comparison has two outcomes, so a sequence of k comparisons can distinguish at most 2ᵏ arrangements. You need 2ᵏ ≥ n!, which gives k ≥ log₂(n!), and that is about n log n.
So merge sort is not merely good. It is within a constant factor of the best any comparison sort can ever be.
The sorts that go faster by not comparing
The floor only applies to comparisons. If you know something about the values themselves you can beat it. Counting sort tallies how many times each value occurs and reads the tally back out, which is O(n + k) for k distinct values. Radix sort applies that digit by digit.
These are not general-purpose. They need bounded, countable keys, and counting sort with a large range costs more memory than the array it is sorting. But when they apply they genuinely beat the floor, because the floor was never about sorting, only about comparing.
Stability, and why it matters more than it sounds
A sort is stable if equal values keep their original order. Merge sort and insertion sort are stable; heap sort and most quicksorts are not.
It matters whenever you sort the same data twice. Sort by name, then by department, and with a stable sort each department is still in name order. With an unstable one that second sort quietly scrambles the first. This is why the sort built into most languages is stable and is specified to be.
What actually ships
Nothing in production is plain merge sort or plain quicksort. Real implementations are hybrids, and the reasons are the ones this lesson and the last one give.
Timsort, which Python and Java use for objects, looks for runs that are already in order and merges them, so nearly sorted input approaches O(n). Introsort, used by most C++ standard libraries, starts with quicksort and switches to heap sort if the recursion gets too deep, which caps the worst case at O(n log n). Both drop to insertion sort on small pieces, because its constant is small enough to win below about sixteen items even though its shape is worse.
Why quicksort, given its worst case
Quicksort is O(n²) in the worst case and was the default sort for decades anyway. Its average is O(n log n) with a smaller constant than merge sort, and it sorts in place where merge sort needs O(n) extra space.
The worst case arrives when the pivot is consistently the smallest or largest value, which is exactly what already-sorted input does to a naive pivot choice. Choosing the median of three, or introsort's escape hatch, is what makes it safe in practice.
Space, and the stack
Merge sort needs somewhere to merge into, so it costs O(n) extra memory. Heap sort matches its time and uses none. Quicksort uses O(log n) stack frames when it splits evenly, and O(n) when it does not, which is the stack-overflow lesson arriving in a new disguise.
Three questions
Pick an answer before you open one. Being wrong here is the useful part, and it is the whole reason to answer rather than read.
Bubble sort needs 91 comparisons on 14 items. Roughly how many will it need on 28?
Merge sort splits the array until each piece holds one item, then merges. Where does the log n in O(n log n) come from?
An array arrives almost in order already. Which sort finishes fastest on it?
Problems
Work them before opening the answers. Reading a solution feels like learning and is not.
Count the passes
Bubble sort on 8 items, worst case.
How many comparisons?Show the answer →Hide the answer
28Seven comparisons on the first pass, six on the next, down to one: 7+6+5+4+3+2+1 = 28, which is n(n-1)/2.
Already sorted
An array is already in order.
What does insertion sort cost? What does merge sort cost?Show the answer →Hide the answer
Insertion sort O(n). Merge sort O(n log n), the same as always.Insertion sort compares each item once with its left neighbour, finds it already in place, and stops. Merge sort has no way to notice and does every level regardless. This is why Timsort looks for runs first.
Which one scrambles your data
Rows sorted by name, then sorted again by department.
One sort is stable and one is not. What is the
difference in the result?Show the answer →Hide the answer
With a stable sort, rows inside each department are still in name order. With an unstable one, that order is lost.Stability is not about correctness of the sort itself, which is fine either way. It is about whether a previous sort survives the next one.
Beating the floor
Sort a million integers, each between 0 and 100.
Can you do better than O(n log n)?Show the answer →Hide the answer
Yes. Counting sort: tally each of the 101 possible values,
then write them back out in order. O(n + k).The n log n floor applies to sorts that work by comparing pairs. Counting sort never compares two elements, so the proof does not cover it. Knowing the keys are bounded is what buys the improvement.
The pivot that kills quicksort
Quicksort always chooses the first element as pivot.
Which input produces its worst case, and why?Show the answer →Hide the answer
An array that is already sorted, or exactly reversed. Every partition puts zero elements on one side, so the depth is n rather than log n, and the cost is O(n²).The most common real input is the one that breaks it, which is why naive quicksort is dangerous rather than merely suboptimal. Median-of-three or a random pivot avoids it; introsort catches it after the fact by watching the depth.
What gets asked, and what a good answer sounds like
Say these out loud rather than reading them. The gap between knowing something and being able to say it is the thing interviews measure.
+Why is merge sort O(n log n)?
The array is halved until each piece holds one item, which takes log n levels, and merging at each level touches every item once, which is the n. One linear pass, log n times.
+Can any sort beat n log n?
Not by comparing pairs. There are n! orderings and each comparison halves the possibilities, so you need at least log₂(n!) comparisons, which is about n log n. Sorts that do beat it, like counting and radix sort, work by inspecting the keys rather than comparing them, and they need bounded keys to do it.
+What is a stable sort and when do you need one?
One that leaves equal elements in their original order. You need it whenever a previous ordering carries information: sort by name then by department, and a stable sort keeps each department in name order while an unstable one discards it.
+Quicksort is O(n²) in the worst case. Why is it everywhere?
Its average is n log n with a smaller constant than merge sort, and it sorts in place rather than needing a second array. The worst case needs a consistently terrible pivot, which median-of-three makes unlikely and introsort catches by switching to heap sort when the recursion gets too deep.
+Which sort would you actually write?
The one in the standard library, and I would say why: it is a hybrid that has already solved the cases I would get wrong. Timsort exploits runs that are already ordered, introsort caps the worst case, and both fall back to insertion sort on small pieces because its constant beats its shape at that size.
Know someone stuck on this? Send it to them.
A classmate, a study group, someone learning this on their own at midnight. The link opens the lesson set up exactly as you have it, the same function and the same number, and runs from the first step so they watch the whole thing build rather than landing in the middle of it.
Also in this course
Big-O: what “grows faster” actually means
Where the two shapes in this lesson come from, measured rather than drawn.
Start there →