Quicksort vs Merge Sort — Which Is Faster? (Visual Comparison)

Ask which sorting algorithm is "the fast one" and you will get two answers: Quicksort and Merge Sort. Both run in O(n log n) time on average, both are divide-and-conquer, and both leave Bubble Sort in the dust. So why do interviewers, textbooks, and standard-library authors keep arguing about them?

Because the average case is where the similarity ends. The two algorithms make opposite trade-offs on worst-case guarantees, memory, stability, and how kindly they treat your CPU cache — and those trade-offs are exactly why real standard libraries use *both*, often welded together inside a single hybrid sort.

Two opposite shapes of divide-and-conquer

The cleanest way to see the difference: Quicksort does its real work before recursing, Merge Sort does its real work after.

Quicksort picks a pivot and partitions the array around it — everything smaller goes left, everything larger goes right. That one pass puts the pivot in its final position forever. Then it recurses on the two halves. By the time the recursion bottoms out, there is nothing left to combine: the array is already sorted in place.

Merge Sort splits first and thinks later. It cuts the array in half, recursively sorts each half, and then merges the two sorted halves by repeatedly taking the smaller front element. The split is trivial; the merge is where every comparison happens — and the merge needs a second array to write into.

quicksort(A, lo, hi):            mergesort(A):
  if lo < hi:                      if length(A) <= 1: return A
    p = partition(A, lo, hi)       left  = mergesort(first half)
    quicksort(A, lo, p - 1)        right = mergesort(second half)
    quicksort(A, p + 1, hi)        return merge(left, right)

  // work happens in partition,    // work happens in merge,
  // BEFORE the recursive calls    // AFTER the recursive calls

Watch both in the visualizer and the shapes are unmistakable: Quicksort locks single elements into place scattered across the array, while Merge Sort builds ever-larger sorted runs — 2, then 4, then 8 — until the final merge zips the whole array together.

Worst case: where Quicksort can betray you

Merge Sort is boringly reliable. It always splits exactly in half, so the recursion is always log n levels deep and every level does O(n) merge work. Sorted input, reversed input, adversarial input — always O(n log n), no exceptions.

Quicksort's O(n log n) depends on the pivot landing somewhere near the middle. If every pivot is the smallest or largest remaining element, each partition peels off just one item, the recursion goes n levels deep, and the total work degrades to O(n²) — Bubble Sort territory. And the classic trigger is embarrassingly common: a naive "pick the first (or last) element" pivot hits its worst case on *already-sorted input*.

Memory: in place vs O(n) extra

Quicksort partitions by swapping elements within the array it was given. Its only overhead is the recursion stack — O(log n) with sensible implementation, which is negligible (about 30 frames for a billion elements).

Merge Sort's merge step fundamentally needs somewhere to put the output while it reads the two inputs, so the standard implementation allocates an O(n) auxiliary array. In-place merging exists in the literature but is complicated and slow enough that nobody ships it. For sorting a large array in tight memory — or on an embedded device — this is a real cost, not a theoretical one.

Stability: the quiet dealbreaker

A sort is stable if elements that compare equal keep their original relative order. Merge Sort is naturally stable: when the merge sees a tie, it just takes from the left half first. Quicksort is not — partitioning flings equal elements across the pivot with no memory of where they started.

This matters the moment you sort real records instead of bare numbers. Sort a spreadsheet by date, then by customer, and a stable sort leaves each customer's rows still date-ordered — you get "grouped by customer, sorted by date within" for free. With an unstable sort, the second pass scrambles the first. This single property is why the sorts that language runtimes expose for *objects* are almost always merge-based.

So why does Quicksort usually win in practice?

Given the O(n²) risk, the instability, and Merge Sort's ironclad guarantee, you might expect Merge Sort to be the default everywhere. It is not, and the reason is hardware, not math. Big-O counts operations; it says nothing about how much each operation costs — and on a modern CPU, the dominant cost is often memory access, not comparison.

• Sequential scans. Partitioning sweeps pointers linearly through one contiguous region — the access pattern hardware prefetchers are built for, so most reads hit cache.
• No second array. Quicksort touches roughly half the memory Merge Sort does per level, because Merge Sort must read from one buffer and write every element into another.
• Tight inner loop. The heart of partition is compare-and-maybe-swap on data already in cache; merging juggles two read heads plus a write head across separate buffers.
• Less data movement overall. In-place swaps beat copying every element between arrays at every one of the log n levels.

None of this shows up in the complexity class — both are O(n log n) on average — but it shows up in constant factors, which is why a well-tuned quicksort typically finishes first on random arrays of primitives. If you want intuition for why constant factors hide inside Big-O, see our visual guide to Big-O notation.

What real standard libraries actually do

The strongest evidence that this is a genuine trade-off, not a quiz question, is that major languages refuse to pick just one:

• C — qsort is unspecified by the standard, but common libc implementations use quicksort variants (glibc notably uses merge sort when memory allows, falling back to quicksort).
• C++ — std::sort is typically introsort: quicksort that switches to heapsort past a depth limit (killing the O(n²) case) and to insertion sort on tiny ranges. std::stable_sort is merge-based.
• Python — sorted() and list.sort() use Timsort, a merge sort tuned to exploit already-sorted runs in real-world data. Stable, guaranteed O(n log n).
• Java — Arrays.sort on objects uses Timsort (stability is required); on primitive arrays it uses dual-pivot quicksort (equal primitives are interchangeable, so stability is moot — take the speed).

Java is the whole debate in one API: where stability matters, merge; where raw speed on primitives matters, quick. Everyone hedges the same way.

Head-to-head comparison

How to choose

• Sorting primitives in memory, want raw speed → Quicksort (with randomized or median-of-three pivots, or full introsort).
• Sorting records where equal keys must keep their order → Merge Sort or Timsort.
• Hard latency guarantees — no tolerable worst case → Merge Sort, or introsort if you need in-place.
• Memory is scarce → Quicksort; the O(n) buffer is Merge Sort's real tax.
• Linked lists, or data too big for RAM → Merge Sort; it only ever needs sequential access.

The verdict

There is no winner, only a trade: Quicksort buys speed with risk, Merge Sort buys guarantees with memory. If you remember one line, make it this — Quicksort is usually faster, Merge Sort is always O(n log n) and stable — and note that the industry's actual answer is "hybridize both". The best way to make that trade-off stick is to watch the two shapes race on the same data.