What is the difference between merge sort and quick sort?
SHORT ANSWER
Merge sort splits the array in half, sorts each half and merges them; it is always O(n log n) and stable but needs O(n) extra space. Quick sort partitions around a pivot in place; it averages O(n log n) but can degrade to O(n squared) with bad pivots.
Explain it simply
Both are divide and conquer, but the hard work happens at different moments.
- Merge sort: split first, work later. Split the pile of answer sheets into halves until each pile has one sheet, then merge sorted piles back together. The merge step does the real work.
- Quick sort: work first, split later. Pick a pivot (one sheet), put smaller sheets on its left and larger on its right, then sort each side the same way. The partition step does the real work.
| Merge sort | Quick sort | |
|---|---|---|
| Time (average) | O(n log n) | O(n log n) |
| Time (worst) | O(n log n) | O(n squared) |
| Extra space | O(n) | O(log n) stack |
| Stable | yes | usually no |
| Good for | linked lists, stable needs, big data on disk | arrays in memory, fast in practice |
Quick sort is often faster in practice because it is cache-friendly and works in place.
Example
text
merge sort: [5 2 4 1] -> [5 2] [4 1] -> [5] [2] [4] [1] -> merge -> [2 5] [1 4] -> [1 2 4 5]
quick sort: [5 2 4 1] pivot 4 -> [2 1] 4 [5] -> sort each sideWhat to say in the interview
"Merge sort guarantees O(n log n) and is stable, at the cost of O(n) extra space. Quick sort sorts in place and is usually faster, but a poor pivot choice on already sorted data gives O(n squared), so I pick a random or median-of-three pivot. For linked lists I prefer merge sort."
Common mistakes
- Saying quick sort is always faster. Its worst case is quadratic.
- Forgetting that merge sort is stable and quick sort usually is not.