Side by side
Merge SortvsQuicksort
What is the difference between merge sort and quicksort?
Updated 2 min read6 differences
In short
Merge sort guarantees O(n log n) time but uses extra memory, while quicksort partitions around a pivot in place and is usually faster, but can slow to O(n²).
Merge Sort
Merge sort is a divide and conquer sorting algorithm that splits a list in half, sorts each half recursively, and merges the sorted halves in O(n log n) time.
Read the page on Merge SortQuicksort
Quicksort is a divide and conquer sorting algorithm that partitions items around a chosen pivot, then sorts the smaller and larger groups the same way.
Read the page on QuicksortMerge Sort and Quicksort compared
| Aspect | Merge Sort | Quicksort |
|---|---|---|
| Strategy | Split in half, sort each half, then merge | Partition around a pivot, then sort each side |
| Average time | O(n log n) | O(n log n), usually faster in practice |
| Worst-case time | O(n log n), guaranteed | O(n²) with consistently bad pivots |
| Extra memory | O(n) for merging arrays | O(log n) for recursion; sorts in place |
| Stability | Stable: equal items keep their order | Not stable in typical implementations |
| Works well on | Linked lists and data too large for memory | Arrays in memory, thanks to good cache use |
The difference, explained
Merge sort and quicksort are both divide-and-conquer sorting algorithms: they break the problem into smaller pieces, solve those and combine the results. Merge sort splits the list into two halves, sorts each one recursively and then merges the two sorted halves. Quicksort picks a pivot element, partitions the list so smaller items go left and larger items go right, and then sorts each side.
They put the hard work in different places. Merge sort's split is trivial and its merge step does the work, which always takes O(n log n) time but needs O(n) extra memory on arrays. Quicksort's partition step does the work in place, using little extra memory and running very fast on average, but if the pivots are consistently poor, such as always the smallest item, it slows to O(n²).
Real-world sort functions often combine them with other algorithms. Introsort starts with quicksort and switches to heapsort if the recursion gets too deep, while Timsort-style algorithms, used in Python and in Java for objects, are built on merge sort and insertion sort.
A common misconception is that quicksort is always the best choice. It is fast on average for arrays in memory, but merge sort is stable (equal items keep their original order), has a guaranteed worst case and suits linked lists and data too large to fit in memory.
Which one should you use?
Choose Merge Sort when…
- You need a stable sort that keeps equal items in order.
- A guaranteed worst case matters more than average speed.
- You are sorting a linked list or data stored on disk.
Choose Quicksort when…
- You are sorting arrays in memory and want top average speed.
- Extra memory is limited.
- Stability does not matter for your data.
Both algorithms in Python
def merge_sort(xs):
if len(xs) <= 1:
return xs
mid = len(xs) // 2
left, right = merge_sort(xs[:mid]), merge_sort(xs[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right): # merge step
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]# Simple version for clarity; production quicksort
# partitions the array in place instead of copying
def quicksort(xs):
if len(xs) <= 1:
return xs
pivot = xs[len(xs) // 2]
smaller = [x for x in xs if x < pivot]
equal = [x for x in xs if x == pivot]
larger = [x for x in xs if x > pivot]
return quicksort(smaller) + equal + quicksort(larger)Readers ask
Which is faster, merge sort or quicksort?
Quicksort is usually faster for arrays in memory because it works in place and uses the CPU cache well. Merge sort wins when you need a guaranteed O(n log n) worst case or are sorting linked lists or very large data.
Is quicksort stable?
Not in its usual in-place form, so equal items may change order. Merge sort is stable, which matters when you sort records by one field and then by another.
Why does quicksort have an O(n²) worst case?
If the pivot is always the smallest or largest item, each partition removes only one element, so the recursion goes n levels deep. Choosing random or median-of-three pivots makes this very unlikely.