Merge Sort vs Quick Sort: What is the Difference?
Compare merge sort and quick sort by time complexity, space, and stability, and learn how to answer this sorting interview question well.
Expected Interview Answer
Merge sort splits an array in half, recursively sorts both halves, then merges them, guaranteeing O(n log n) time and stability at the cost of O(n) extra space; quick sort partitions around a pivot in place, averaging O(n log n) with O(log n) space but degrading to O(n²) on poor pivot choices.
Merge sort’s divide step is trivial and its merge step does the real work of combining two sorted halves, which makes it predictable and stable — equal elements keep their relative order. Quick sort’s partition step does the real work up front, rearranging elements around a pivot so smaller values land left and larger values land right, then recurses on each side in place. Quick sort is usually faster in practice due to better cache locality and lower constant factors, while merge sort’s guaranteed worst case and stability make it preferred for linked lists, external sorting, and when stability matters. Randomized or median-of-three pivot selection is the standard fix for quick sort’s worst-case risk.
- Merge sort guarantees O(n log n) worst case
- Merge sort is stable, preserving equal-element order
- Quick sort sorts in place with O(log n) space
- Quick sort typically has better real-world constant factors
AI Mentor Explanation
Merge sort is like splitting a stack of scorecards into two piles, having two scorers independently sort their pile, then a third scorer carefully interleaving the two sorted piles back into one — always the same predictable effort. Quick sort is like picking one scorecard as a reference score, quickly tossing every card lower than it to the left and higher to the right, then repeating on each smaller pile in place. Merge sort always takes a steady, predictable amount of work no matter how the cards started. Quick sort is usually faster because there’s no separate merging step, but a badly chosen reference card can leave one pile almost as big as the original, slowing things down.
Step-by-Step Explanation
Step 1
Merge sort: divide
Split the array into two halves recursively until each has one element.
Step 2
Merge sort: conquer
Merge each pair of sorted halves back together in O(n) per level, O(n log n) total.
Step 3
Quick sort: partition
Choose a pivot, rearrange elements so smaller are left and larger are right, in place.
Step 4
Quick sort: recurse
Recursively partition each side; average O(n log n), worst case O(n²) with a bad pivot.
What Interviewer Expects
- State time complexities: merge sort always O(n log n); quick sort average O(n log n), worst O(n²)
- Explain space: merge sort O(n) extra, quick sort O(log n) in place
- Mention merge sort is stable, quick sort typically is not
- Give a use-case reason to prefer one (linked lists/stability vs cache locality/memory)
Common Mistakes
- Claiming quick sort is always faster with no mention of worst case
- Forgetting merge sort needs O(n) auxiliary space
- Not knowing quick sort is not stable by default
- Confusing the divide step (trivial) with the combine step (does the work) between the two algorithms
Best Answer (HR Friendly)
“Merge sort splits the data in half, sorts each half, and carefully combines them back together, so it is always predictable but needs extra memory. Quick sort picks a pivot and rearranges elements around it in place, so it is usually faster and uses less memory, but can slow down if the pivot choices are unlucky.”
Code Example
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if 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]
quick_sort(arr, lo, i - 1)
quick_sort(arr, i + 1, hi)
return arrFollow-up Questions
- How would you make quick sort’s worst case less likely?
- Why is merge sort preferred for sorting linked lists?
- What does it mean for a sort to be stable, and why does it matter?
- How would you sort data too large to fit in memory?
MCQ Practice
1. What is the worst-case time complexity of quick sort?
A consistently bad pivot choice (e.g. always the smallest or largest element) degrades quick sort to O(n²).
2. Which sorting algorithm is stable by default?
Merge sort preserves the relative order of equal elements during the merge step; quick sort typically does not.
3. What is the extra space complexity of standard merge sort?
Merge sort needs auxiliary arrays to hold the merged results, giving O(n) extra space.
Flash Cards
What is merge sort’s guaranteed time complexity? — O(n log n), in every case (best, average, worst).
What is quick sort’s worst-case time complexity? — O(n²), when pivots consistently split poorly.
Which of the two is stable by default? — Merge sort is stable; quick sort is not, by default.
Which sort uses less extra memory? — Quick sort, which sorts in place with O(log n) space vs merge sort’s O(n).