Quicksort vs Mergesort: Sorting Algorithms Explained

Quicksort and mergesort are both divide-and-conquer sorting algorithms that run in O(n log n) time on average, but they get there in fundamentally different ways: quicksort partitions data around a pivot and sorts in place, while mergesort splits data in half, recursively sorts each half, and merges the results using extra memory. That structural difference is why the same asymptotic complexity produces such different real-world performance profiles.

The shared idea: divide and conquer

Both algorithms attack the sorting problem the same high-level way — break a large unsorted list into smaller pieces, sort the pieces, and combine them. This is the same strategy that shows up in dynamic programming and in tree-based algorithms generally, including traversals over a binary search tree: solve small subproblems and build the answer up from there. Understanding why divide-and-conquer beats a naive O(n²) approach like bubble sort is part of what Big O notation is designed to make precise.

How mergesort works

Mergesort splits the input array in half repeatedly until each piece has a single element — trivially sorted — then merges pairs of sorted pieces back together, comparing the front elements of each pair and taking the smaller one first. The merge step is the whole algorithm’s engine: given two already-sorted lists, merging them into one sorted list takes linear time, and because the recursion always splits evenly in half, the total work comes out to O(n log n) in every case — best, average, and worst.

That worst-case guarantee is mergesort’s headline strength. No input, however adversarial, can push mergesort past O(n log n). The cost is memory: the merge step typically needs a temporary array to hold the merged output before copying it back, so a standard mergesort implementation uses O(n) additional space.

How quicksort works

Quicksort picks a pivot element and partitions the rest of the array into two groups: everything smaller than the pivot, and everything larger. It then recursively sorts each group, and because the partitioning happens in place, no extra array is needed — quicksort commonly runs with just O(log n) additional space for its recursion stack, far less than mergesort’s O(n).

The catch is that partition quality depends entirely on pivot choice. If the pivot consistently splits the data close to evenly, quicksort runs in O(n log n), typically with lower constant-factor overhead than mergesort because it avoids the copying involved in a merge step — which is why quicksort is often faster in practice on random data. But if the pivot is consistently the smallest or largest element — which happens on already-sorted input if you naively pick the first element as pivot every time — the partitions become wildly unbalanced and the algorithm degrades to O(n²).

Real-world implementations guard against this with better pivot selection strategies, such as picking a random element or the median of three candidates, which makes the worst case exceedingly unlikely in practice even though it’s still theoretically possible.

Stability

A sorting algorithm is stable if it preserves the relative order of equal elements — important when sorting records by one field while wanting ties broken by original order (say, sorting a list of orders by date, where same-date orders should stay in their original sequence). Mergesort is naturally stable: the merge step can always be written to prefer the earlier list when values are equal. Standard in-place quicksort is not stable — the partitioning step swaps elements around in ways that can reorder equal elements. Stable variants of quicksort exist but usually give up quicksort’s in-place memory advantage to get there.

Quicksort vs mergesort at a glance

	Quicksort	Mergesort
Average time	O(n log n)	O(n log n)
Worst-case time	O(n²)	O(n log n)
Extra space	O(log n)	O(n)
Stable	No (standard implementation)	Yes
Typical practical speed	Faster (lower overhead)	Slower (merge copying)
In-place	Yes	No (standard implementation)

Why the choice still matters today

Most general-purpose language standard libraries don’t use a pure version of either algorithm — they use hybrids tuned for real-world data. Many array-sorting implementations use an introspective approach that starts with quicksort for speed but falls back to a guaranteed-O(n log n) algorithm like heapsort if the recursion depth suggests a bad pivot pattern, borrowing ideas from structures like a heap. Many implementations that sort objects or require stability — Python’s sort() and Java’s Collections.sort() for objects, for instance — use a mergesort-family algorithm specifically because stability matters when sorting real-world records, and because worst-case guarantees matter more for library code that has to handle arbitrary user input safely.

External sorting — sorting data too large to fit in memory, such as sorting rows in a database — leans on mergesort’s structure almost by necessity, since merging sorted chunks read sequentially from disk is far cheaper than the random access patterns quicksort’s partitioning requires. This is conceptually related to how a database might build a materialized view or maintain a sorted index behind the scenes to avoid resorting data on every query.

Which one to reach for

If you’re calling a language’s built-in sort, this choice has usually already been made for you by people who benchmarked it carefully — the practical answer is almost always “use the standard library’s sort.” If you’re implementing sorting yourself, understanding the tradeoff still matters: reach for quicksort’s in-place efficiency when memory is tight and worst-case blowup is acceptable or defended against with good pivot selection, and reach for mergesort when you need a guaranteed worst case, stability, or you’re sorting data that doesn’t fit comfortably in memory.

The takeaway

Quicksort and mergesort both achieve O(n log n) average performance through divide-and-conquer, but they make opposite tradeoffs: quicksort sorts in place with less memory and typically less overhead, at the risk of O(n²) behavior on bad pivot choices, while mergesort guarantees O(n log n) in every case and preserves stability, at the cost of needing extra memory for the merge step. Most real-world library sorts are hybrids that borrow the best of both, but the underlying tradeoff is still the reason those hybrids exist.