Why is quicksort faster than merge sort in practice
Why is quicksort faster than merge sort in practice, when both are O(n log n) on average? Quicksort actually does more comparisons. It wins on memory traffic, footprint and loop tightness, and loses the moment comparisons get expensive or stability matters.
Why is quicksort faster than merge sort in practice? Both average O(n log n), but quicksort partitions in place over contiguous memory, moves fewer elements, and runs a very tight inner loop. Merge sort pays for a temporary buffer and for copying every element at every level. The gap is a constant factor, not a better exponent.
I want to be careful with that claim, because it usually gets repeated far too loosely. Quicksort is not asymptotically better. It is not even doing less work by the usual count. On random arrays of machine integers, a well-engineered quicksort beats a well-engineered merge sort by something like 10% to 50%, depending on size, language and hardware. On other inputs the order flips. The interesting part is why the constant factor lands where it does, and which of your inputs break the pattern.
Here is the framing I use. Imagine sorting a long shelf of books. Quicksort is the librarian who picks a marker book and walks the shelf from both ends, swapping any book on the wrong side of the marker, right there on the shelf. Merge sort is the librarian who insists on a second empty shelf of the same length, and carries every book across to it at every round. Both finish in about log n rounds. One of them is hauling twice as much furniture.
Does quicksort really do fewer operations than merge sort?
No. Quicksort does more comparisons than merge sort, and wins anyway because comparisons are not the expensive part of sorting integers.
Take the textbook numbers. Merge sort on n elements uses slightly under n log2 n comparisons, in the best and worst case alike. Quicksort with a random pivot averages about 2 n ln n, which is roughly 1.39 n log2 n. Choosing the median of three candidates as the pivot brings that down to about 1.19 n log2 n, and it is the standard engineering fix.
For n = 10 million, log2 n is about 23.3. That gives merge sort around 2.2 x 10^8 comparisons, quicksort with a random pivot around 3.2 x 10^8, and quicksort with median of three around 2.8 x 10^8. So quicksort performs somewhere between 27% and 45% more comparisons, and still tends to finish first on plain integer arrays. If you only count comparisons, you predict the wrong winner. That should tell you the model is missing something, which is the point of the next section.
What does each algorithm cost besides comparisons?
Mostly element movement and memory footprint. A comparison between two integers already in registers costs about one cycle. Moving data through memory is where the time goes.
Count the writes for the same 10 million element array of 4-byte integers. Top-down merge sort has about 24 levels (log2 of 10^7, rounded up). At each level, every element is written into the auxiliary buffer, so you get roughly 2.4 x 10^8 element writes, plus whatever copying back the implementation does. The buffer itself is 40 MB of extra memory, and touching fresh pages for the first time has its own cost.
Quicksort exchanges only the pairs that are on the wrong side of the pivot. A common estimate is about a third of n ln n exchanges, which is roughly 5 x 10^7 here. Each exchange writes two elements, so you land near 10^8 element writes: less than half of merge sort's total, with no auxiliary array at all. Elements that are already on the correct side are never touched, and with random data about half of them are.
That asymmetry is the first real reason. Merge sort moves every element at every level, unconditionally. Quicksort moves only the ones that need moving.
Where does the cache come into it?
The cache matters through footprint, not through access pattern. Both algorithms are sequential scanners, so the hardware prefetcher is happy with either.
Partitioning reads from the left and right ends toward the middle: two sequential streams over one array. A merge reads two sorted runs and writes a third stream into the buffer: three streams over two arrays. Neither has the random jumping that makes linked lists or heapsort slow. The difference is that merge sort's working set is twice the size of the data.
Suppose your L2 cache is 1 MB, holding 262,144 four-byte integers. Quicksort's subproblems fit once they are below about 262,000 elements. Merge sort needs the subarray plus its buffer, so it fits below about 131,000. From 10 million elements, quicksort needs about 5.3 levels of halving to get cache-resident, merge sort about 6.3. That leaves roughly 18 of 24 levels running from cache for either algorithm, which is why the end-to-end gap is modest rather than dramatic. If someone tells you quicksort is three times faster because of the cache, they have not done this arithmetic.
The rest of the gap is loop tightness. A partition loop is a handful of instructions: load, compare to the pivot, advance a pointer, occasionally swap. There is no allocation, no copy-back phase and no bookkeeping about which run an element came from. Branch misprediction is not a differentiator, by the way. Both algorithms make a roughly 50/50 data-dependent branch per element on random input. Modern implementations of both go to some lengths to make that branch-free.
As an illustration, on a laptop-class machine sorting 10 million random 32-bit integers, I would expect something like 0.8 seconds for C++ std::sort (introsort) against 1.0 to 1.1 seconds for std::stable_sort (merge-based). Treat those as the shape of the result, not a benchmark. Run it on your own hardware before quoting a number to anyone.
Doesn't quicksort have a quadratic worst case?
Yes, and it is the price of the speed. A bad pivot splits the array into sizes 1 and n-1, and the recursion degenerates to O(n^2).
Take a naive quicksort that always picks the first element as the pivot, and feed it an already sorted array of 100,000 elements. Every partition peels off one element, so the comparison count is about n(n-1)/2, or 5 x 10^9. A healthy run needs about n log2 n, roughly 1.7 x 10^6. That is a factor of 3,000. The recursion also goes 100,000 frames deep, which will overflow the stack in many languages before the slowness even registers.
Real implementations defend against this in three layers:
- Better pivot choice. Random pivot, or median of three (first, middle, last). Sorted and reverse-sorted inputs stop being adversarial.
- Introsort. Track recursion depth, and if it exceeds about 2 log2 n, switch that subarray to heapsort. The worst case is capped at O(n log n).
- Bounded stack. Recurse into the smaller partition, loop on the larger one. Stack depth never exceeds log2 n.
Duplicates are the other trap. A Lomuto-style partition on an array of 100,000 equal values puts everything on one side and goes quadratic. The Hoare scheme stops on equal elements and swaps them, which splits evenly. Here is the Hoare partition that most production code descends from:
def partition(a, lo, hi):
pivot = a[(lo + hi) // 2]
i, j = lo - 1, hi + 1
while True:
i += 1
while a[i] < pivot:
i += 1
j -= 1
while a[j] > pivot:
j -= 1
if i >= j:
return j
a[i], a[j] = a[j], a[i]
When your data has heavy duplication, a three-way partition (less than, equal to, greater than) is better still. The Dutch national flag idea is exactly that, and it turns an array with only a few distinct keys into a near-linear sort.
When is merge sort the better choice?
Merge sort wins when you need stability, when the data is not in a random-access array, or when comparisons are expensive. Those three cases cover a lot of real code.
Expensive comparisons. Count comparisons again, but for 1 million objects compared through a callback or a string comparison. Merge sort needs about 1.87 x 10^7 comparisons; quicksort with a random pivot about 2.76 x 10^7. The difference is 9 million comparisons. If each costs 100 nanoseconds, that is nearly 0.9 seconds in merge sort's favour, and the cache argument is now noise. This is why Python's sorted and Java's sort for objects use merge-based algorithms (Timsort), which also exploit existing runs in the input to do fewer comparisons still.
Stability. Sorting records by one key while preserving a previous order on another is routine: sort by date, then stably by customer. Standard quicksort is not stable, and making it so costs the in-place advantage.
Linked lists. Merging two sorted lists only relinks pointers, so merge sort needs no auxiliary array, and it never needs random access. Quicksort's partition has no such luck, and the cache-friendliness argument evaporates anyway, as why arrays beat linked lists in practice explains. If you want to practise that exact merge step, merge two sorted lists is the cleanest place to do it.
Guarantees and scale. Merge sort has a hard O(n log n) bound with no pivot heuristics, and it adapts naturally to external sorting, where chunks are sorted in memory and merged from disk, and to parallel sorting, where halves are independent.
How do the common sorts compare?
Here is the side-by-side, using the typical engineered versions of each rather than the textbook ones.
| Algorithm | Average comparisons | Worst case | Extra space | Stable | Memory behaviour |
|---|---|---|---|---|---|
| Quicksort (median of three) | about 1.19 n log2 n | O(n^2) unless introsort | O(log n) stack | No | Two sequential streams, in place |
| Merge sort (top-down) | about n log2 n | O(n log n) | O(n) buffer | Yes | Three streams, double footprint |
| Timsort | at most about n log2 n, far fewer on partly ordered data | O(n log n) | up to O(n) | Yes | Sequential runs, galloping merges |
| Heapsort | about 2 n log2 n | O(n log n) | O(1) | No | Parent and child far apart, poor locality |
Heapsort is the instructive row. It has the best theoretical profile of the four on paper (in place, guaranteed bound) and is usually the slowest in practice, because its access pattern jumps across the array. It is a good reminder that the number of operations is not the same as the time they take. If you sort partially to get the top few items, that is a different tool entirely, and when to use a heap instead of sorting covers it.
What should you say about this in an interview?
Say that the two have the same asymptotic average, that quicksort wins by a constant factor from in-place partitioning and lower memory traffic, and that merge sort wins on stability, guaranteed bounds, linked lists and expensive comparisons. Then name the worst case and its fix. That answer takes thirty seconds and shows you know the difference between a bound and a measurement.
What you should avoid is the one-line version, quicksort is faster because of the cache. As the arithmetic above shows, most of both algorithms' levels run from cache anyway. The honest explanation is a stack of small effects: fewer element moves, half the footprint, no copy-back, a tiny loop. Each is worth 10% to 30%, and together they decide a race that is rarely wider than 2x.
Frequently asked questions
Is quicksort always faster than merge sort?
No. It is faster on random arrays of cheap-to-compare values, typically by 10% to 50%. For objects with expensive comparisons, for linked lists, and for data with long pre-sorted runs, a merge-based sort is usually faster, and it is the only one of the two that is stable.
Which sort do Python, Java and C++ actually use?
Python uses Timsort, a merge-based hybrid, for everything. Java uses a dual-pivot quicksort for primitive arrays and Timsort for object arrays. C++ std::sort is typically introsort, and std::stable_sort is merge-based. The split follows exactly the stability and comparison-cost trade-off described above.
Can quicksort be made stable?
Yes, but not for free. You can partition into a separate buffer in order, or tag each element with its original index and break ties on it. Either approach costs the in-place property or extra memory, which removes much of the reason to choose quicksort over merge sort in the first place.
The partition step reaches well beyond sorting, and the best next step is to see it reused to find the k-th smallest element in expected linear time: read the quickselect walkthrough