Quicksort and mergesort both guarantee O(n log n) time on average and get taught back to back, which makes it easy to assume they are interchangeable. They are not. One sorts in place and can blow up to O(n²) on the wrong input; the other never does, but pays for that guarantee in memory. Here is what actually separates them and which one to reach for.
What changed in 2026
- Fewer engineers hand-roll either one in production. AI-assisted code review now reliably flags naive pivot selection (always picking the first or last element) as a performance risk, pushing more teams toward the language built-in sort instead of a custom implementation.
- Hybrid sorts remain the default everywhere. No mainstream standard library ships a textbook-pure quicksort or mergesort; the trend toward hybrids (Timsort-style stable sorts, pattern-defeating quicksort variants) has only deepened.
- Interview questions lean toward tradeoffs, not recitation. Explaining why you would pick one over the other, out loud, is now at least as common as implementing either from memory.
- External and streaming sorts still matter. Merge-based external sorting stays relevant for data too large to fit in memory, even though quicksort dominates in-memory work.
How quicksort works
Pick a pivot, partition the array so everything smaller than the pivot ends up left of it and everything larger ends up right of it, then recurse on each side. The partition step itself is a two-pointer scan — see two-pointer technique explained for the general pattern it borrows.
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
Quicksort sorts in place, using only O(log n) extra space for the recursion stack. Its downside: a poor pivot choice on already-sorted or adversarial data produces lopsided partitions and O(n²) behavior. Randomizing the pivot, or picking the median of three candidates, makes that worst case practically unreachable.
How mergesort works
Split the array in half, recursively sort each half, then merge the two sorted halves back together.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps equal elements stable
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
Mergesort always finishes in O(n log n), regardless of input order, because the split point never depends on the data. The cost is O(n) extra space for the merge step, and it is naturally stable — equal elements keep their original relative order, which quicksort does not guarantee.
Quicksort vs mergesort at a glance
| Property |
Quicksort |
Mergesort |
| Average time |
O(n log n) |
O(n log n) |
| Worst case |
O(n²) |
O(n log n) |
| Extra space |
O(log n), recursion stack |
O(n) |
| Stable |
No, in the standard form |
Yes |
| In-place |
Yes |
No, in the standard form |
| Best fit |
Arrays, in-memory sorting |
Linked lists, external/disk sorting |
When to reach for each
Use quicksort-family sorting when data fits in memory, stability does not matter, and average speed matters more than a worst-case guarantee — why most in-memory array sorts default to it. Use mergesort when you need guaranteed O(n log n) regardless of input, when stability matters, or when data lives on disk or in a linked list where in-place partitioning is not cheap.
In practice, few languages make you choose directly. Python sorted() and Java Arrays.sort() for objects use Timsort, a stable merge-based hybrid. C++ std::sort typically uses introsort, a quicksort variant with a heapsort fallback to avoid the O(n²) worst case. Check current documentation for your language if the exact guarantee matters.
Common pitfalls
Assuming a language sort is unstable because it is basically quicksort. Python and Java both guarantee stability for their default object sorts.
Picking a fixed pivot (first or last element) in production code. On sorted or reverse-sorted input, this triggers the quicksort worst case every time. Randomize the pivot or use median-of-three.
Choosing quicksort when stability is a silent requirement. Equal sort keys that must keep their relative order will silently come out wrong under a non-stable quicksort.
FAQ
Is Python sort() a quicksort?
No. Python uses Timsort, a stable hybrid of merge sort and insertion sort that takes advantage of existing runs of order in real data.
Which is faster in practice?
Quicksort family algorithms usually win on in-memory arrays thanks to cache locality and no allocation overhead. Mergesort wins when the worst-case guarantee or stability matters more than raw average speed.
What is introsort?
A hybrid that starts as quicksort, switches to heapsort if recursion goes deeper than expected (avoiding O(n²)), and uses insertion sort for small subarrays.
Do interviews still expect me to implement these from memory?
Often yes for mid-level and senior roles, but explaining the tradeoffs correctly matters just as much.
Where to go next