Skip to content
Essay · Complexity

Why is quicksort faster than merge sort?

Why is quicksort faster than merge sort when merge sort does fewer comparisons? A worked example with a million integers shows where the time goes: data movement, cache footprint and branch misprediction, not comparison counts.

By Vishy10 min readPublished · 11 Nov 2026

Why is quicksort faster than merge sort when merge sort does fewer comparisons? Because comparisons are not the bottleneck on real hardware. Quicksort partitions in place, so it reads and writes memory in tight sequential sweeps that stay in cache, while merge sort copies every element through a second buffer at every level of recursion.

Is quicksort actually faster than merge sort?

For arrays of fixed-size values in memory, yes, and by a margin you can measure: roughly 1.2x to 1.6x on random data, more when the pivot rule and the compiler are good. That sentence has conditions on purpose. The claim fails for linked lists, for sorts that must be stable, and for data whose comparisons are expensive, and I will cover each of those. But the default belief, that quicksort is the fast general-purpose array sort, survives measurement.

What does not survive is the usual explanation. Plenty of answers say quicksort wins because merge sort needs extra memory, and stop there. Extra memory is real, but the full account has four parts: comparison count, data movement, cache footprint and branch behaviour. Merge sort wins exactly one of them. Quicksort wins the others by small margins that multiply.

The textbook model is the reason this confuses people. Asymptotic analysis counts abstract operations and treats them as equal in cost. Both algorithms are Θ(n log n) on average, so on paper they tie, and any real gap must come from constants the notation throws away. This is the same point I make in Complexity is a contract, not a fact: a bound tells you how cost grows, not what it is at the size you actually have.

Doesn't merge sort do fewer comparisons?

Yes, and the gap is larger than most people expect. Take n = 1,000,000 distinct integers in random order. Then log2 n is about 19.93, and the average comparison counts work out like this:

  • Merge sort: about n log2 n minus 1.25n, which is 19.93 million minus 1.25 million, roughly 18.7 million comparisons.
  • Quicksort with a random pivot: about 2 n ln n, which is roughly 27.6 million comparisons. That is 48 percent more than merge sort.
  • Quicksort with a median-of-three pivot: about 1.19 n log2 n, roughly 23.7 million. Better, but still 27 percent more.

If comparisons were all that mattered, merge sort would win by a quarter to a third. It does not win, because comparing two integers that are already in registers costs a fraction of a nanosecond, and almost everything around that comparison costs more.

Now count data movement. Merge sort with a scratch buffer has ceil(log2 1,000,000) = 20 levels, and at each level every element is written once into the other buffer. That is about 20 million writes, plus 20 million reads from the source runs. Quicksort with Hoare-style partitioning swaps only the elements that are on the wrong side of the pivot. The average is about one third of n ln n swaps, which is roughly 4.6 million swaps, or about 9 million writes. It reads every element at each level too, but reading is cheap when the access is sequential. So quicksort does somewhat more comparing and about half as much writing.

Footprint matters as well. A million 4-byte integers occupy 4 MB. Merge sort needs that plus a 4 MB buffer, 8 MB in total, which does not fit in a typical per-core L2 cache of 256 KB to 1 MB and may crowd a shared L3. Quicksort touches only the original 4 MB, and after about four levels of partitioning (1,000,000 divided by 16 is 62,500 elements, around 250 KB) each subarray fits in L2. The remaining sixteen or so levels run almost entirely out of cache.

Here is where I want to be honest, because the folklore overstates it. Merge sort's lower levels also fit in cache, and its three sequential streams (two input runs, one output) are exactly what hardware prefetchers handle well. The cache argument is real but modest. On a recent laptop, a good introsort-style sort of a million random ints runs somewhere around 65 to 80 ms, and a top-down merge sort with one scratch buffer around 85 to 115 ms. Reproduce those numbers on your own machine rather than trusting mine, but expect the same ordering and a gap of that general size.

What does the memory hierarchy have to do with it?

It decides how expensive each move is, and merge sort makes more moves per element. A load that hits L1 costs about 4 cycles, roughly a nanosecond. A load that goes to main memory costs on the order of 80 to 100 nanoseconds, nearly a hundred times more. Sequential access hides most of that latency through prefetching, but writes and footprint still cost bandwidth.

Here is the framing I use. Imagine sorting a pile of parcels by weight. Quicksort is working in the one room you are standing in: pick a reference parcel, push lighter ones to the left wall and heavier ones to the right, and only touch a parcel when it is on the wrong side. Merge sort is carrying every parcel to a second room at every round, merging two sorted stacks as you drop them off, then carrying them all back for the next round. The carrying is the cost. Twenty rounds of carrying a million parcels is twenty million trips, even when each trip is short and the route is perfectly straight. Quicksort moves only the parcels that are in the wrong place, and as the piles get small it never leaves the corner of the room.

That is also why array layout matters so much to both algorithms. Contiguous memory is the precondition for any of this, a theme I develop in Why arrays beat linked lists in practice. Change the container to a linked list and the entire argument reverses, as I show below.

The inner loop of the partition step is small enough to memorise, and its smallness is part of the speed:

def partition(a, lo, hi):\n    pivot = a[(lo + hi) // 2]\n    i, j = lo - 1, hi + 1\n    while True:\n        i += 1\n        while a[i] < pivot:\n            i += 1\n        j -= 1\n        while a[j] > pivot:\n            j -= 1\n        if i >= j:\n            return j\n        a[i], a[j] = a[j], a[i]\n

Two indices walk toward each other, each doing a compare and an increment. Nothing is copied unless a swap is needed. Compare that to the merge loop, which on every step compares the heads of two runs, copies the winner, advances one of three pointers, and checks whether either run is exhausted. That is more instructions per element per level, and it runs at every level.

Doesn't quicksort suffer from branch mispredictions?

It does, badly, and this is the largest single cost in the classical algorithm. Against a random pivot, each comparison is close to a coin flip, so the branch predictor guesses wrong about half the time. A misprediction costs around 15 cycles. Do the arithmetic for our example: 27.6 million comparisons, times 0.5 mispredicted, times 15 cycles, is about 207 million cycles, or around 70 ms at 3 GHz. That is nearly the whole runtime I quoted. It is a back-of-the-envelope figure, but it explains why measured times land where they do.

Merge sort has the same problem inside its merge step, since choosing which run supplies the next element is also unpredictable. With 18.7 million comparisons the same estimate gives about 47 ms of misprediction. That is lower than quicksort's, which is a fair point for merge sort, and it is why the end-to-end gap is 1.2x to 1.6x rather than 3x. Quicksort wins on moves and footprint and gives back some of that on mispredictions.

The interesting consequence is that the best modern sorts attack exactly this cost. Block-based and branchless partitioning schemes compute comparison results into a small buffer of offsets and then do the swaps without data-dependent branches. Pattern-defeating quicksort uses that idea and reaches times well under what the classical algorithm manages. Branchless merging with conditional moves exists too. The lesson is that speed here is a property of the implementation as much as the algorithm, and the textbook version of either is not what ships in your standard library.

When is merge sort the better choice?

Merge sort is better whenever stability matters, whenever comparisons are expensive, whenever random access is unavailable, or whenever you need a hard worst-case guarantee without extra machinery. Four situations, each with a reason.

Expensive comparisons. Suppose each comparison calls a comparator that dereferences two objects and compares strings, costing 200 ns, while a move costs 1 ns. Then the 8.9 million extra comparisons that quicksort performs (27.6 million minus 18.7 million) cost about 1.8 seconds, which swamps every saving on the data-movement side. When the comparison dominates, fewer comparisons wins outright. This is why Python's sort for arbitrary objects uses Timsort, a merge-based algorithm that also exploits existing runs.

Stability. A stable sort keeps equal keys in their original order, which you need when sorting records by one field after another. Quicksort's long-distance swaps destroy that order. Merge sort preserves it for free if ties are taken from the left run.

Linked lists. Merging two sorted lists needs no scratch buffer and no random access; you relink nodes in O(1) extra space, as in merging two sorted lists. Quicksort's partition wants to walk from both ends, which a singly linked list cannot do cheaply. For lists, merge sort is the natural choice, and the cache penalty of pointer chasing hits both algorithms equally.

External data. When the data lives on disk and does not fit in memory, you sort chunks that fit, write them out as runs, and merge the runs sequentially. Merging reads each run front to back, which is what disks and network storage do well.

The table below puts the common options side by side for n = 1,000,000.

AlgorithmAverage comparisonsExtra spaceStableWorst caseBest fit
Quicksort, median-of-threeabout 23.7MO(log n) stackNoO(n²)Arrays of primitives
Introsort or pdqsortabout 20M to 24M, fewer on patterned dataO(log n) stackNoO(n log n)Default unstable array sort
Top-down merge sortabout 18.7MO(n) bufferYesO(n log n)Stable sort, costly comparisons
Merge sort on a linked listabout 18.7MO(log n) recursion, relinking in placeYesO(n log n)Linked lists
Heapsortabout 2 n log2 n, roughly 40MO(1)NoO(n log n)Hard memory limit and worst-case bound
Timsortbetween n minus 1 and about 18.7MO(n) bufferYesO(n log n)Partly ordered data, object sorting

How do real libraries keep quicksort fast without its worst case?

They combine it with other algorithms and with a few cheap defences. The worst case is not a theoretical footnote. If you pick the first element as pivot and feed it already-sorted input, every partition splits into sizes 0 and n minus 1. For n = 1,000,000 that is about n²/2, or 5 x 10^11 comparisons, which at one nanosecond each is over eight minutes, and a recursion depth of a million frames that will overflow most stacks long before it finishes.

The standard defences are cheap:

  • Better pivots. Median-of-three, or a pseudo-median of nine samples on large ranges, makes sorted and reverse-sorted input harmless and trims the average comparison count.
  • Recurse on the smaller half. Handle the smaller partition recursively and loop on the larger one. The stack depth is then at most log2 n, which is 20 for our million elements.
  • Introsort fallback. Count recursion depth, and if it exceeds about 2 log2 n (40 here), switch that subrange to heapsort. The worst case becomes O(n log n) with almost no cost on normal inputs.
  • Insertion sort for small ranges. Below roughly 16 elements, insertion sort beats further partitioning because its loop is tiny and perfectly cache-resident.
  • Three-way partitioning. If the data has many duplicates, grouping equal keys together avoids quadratic behaviour on inputs like a million copies of five values. That is the Dutch national flag idea.

This is why Java's Arrays.sort on primitive arrays uses a dual-pivot quicksort, while the same call on object arrays uses a merge-based Timsort, and why Rust offers a stable merge-style sort and a separate sort_unstable built on pattern-defeating quicksort. The library authors made the same trade-offs this essay describes: unstable and fast for primitives, stable and comparison-frugal for objects. If your keys are small integers, both lose to non-comparison methods; see counting and radix sort for when that applies.

Frequently asked questions

Is quicksort always faster than merge sort?

No. It is usually faster on in-memory arrays of primitive values, but merge sort wins when comparisons are expensive, when the sort must be stable, when the data is a linked list, or when the data lives on disk. On partly ordered input, Timsort can also beat both by detecting runs that are already sorted.

If quicksort can be O(n²), why is it still the default in so many libraries?

Because the quadratic case is avoidable with cheap measures: a median-based pivot, recursing on the smaller side, and a heapsort fallback when depth grows past about 2 log2 n. With those in place the worst case is O(n log n), and the average-case speed of the in-place partition loop is kept.

Which one should I write in a coding interview?

Write merge sort if the problem involves linked lists or stability, since its correctness argument is the easiest to state. Write quicksort when the interviewer asks about in-place sorting or selection, because the partition step is also the engine behind finding the k-th element in expected linear time. Learn partition well, then see it reused in quickselect.