Quicksort vs Merge Sort
Quicksort is faster in practice on arrays and is what most standard libraries use for primitives. Merge sort is the one to pick when you need a guaranteed O(n log n), a stable sort, or you are sorting a linked list.
Both average O(n log n), and the textbook comparison stops there, which is why the answer sounds arbitrary. The real differences are the worst case, the memory, and whether equal elements keep their original order. Java itself picks between them by element type: dual-pivot quicksort for primitives, a merge sort variant for objects.
Side by side
| Dimension | Quicksort | Merge Sort |
|---|---|---|
| Average time | O(n log n) | O(n log n) |
| Worst case | O(n squared) on a bad pivot | O(n log n) always |
| Extra space | O(log n) for the recursion | O(n) for the merge buffer |
| Stable | No | Yes, when the merge favours the left half |
| Cache behaviour | Good, scans are sequential | Worse, the merge buffer doubles the traffic |
| Linked lists | Poor, partitioning needs random access | Natural, only sequential access is needed |
| Java uses it for | int[], long[], other primitives | Object[], via TimSort |
When to pick each
Quicksort
- Sorting an array in memory where average speed matters more than the worst case.
- Memory is tight and the O(n) merge buffer is not affordable.
- Elements are primitives, where stability cannot be observed anyway because two equal ints are indistinguishable.
Merge Sort
- A guaranteed bound is required, for instance in anything with a latency budget.
- Stability matters, such as sorting by one key after already sorting by another.
- The input is a linked list, where merge sort needs no random access and quicksort's partition would be O(n) per level of traversal.
- The data does not fit in memory, since external sorting is merge sort by another name.
Assuming the O(n squared) case is a theoretical curiosity. It is triggered by already-sorted input when the pivot is the first or last element, and already-sorted input is extremely common in real data. A random pivot or median-of-three makes it vanishingly unlikely, and this is exactly what an interviewer is checking when they ask about the worst case.
Questions people ask
Why does Java use both?
Stability is only observable when equal elements carry other data. Two equal ints are interchangeable, so primitives get quicksort for its speed. Objects can be equal by comparator and different in every other field, so they get a stable merge sort.
Is quicksort really faster if both are O(n log n)?
Yes, and the reason is constants rather than complexity. Quicksort partitions in place with sequential access, which the cache handles well. Merge sort writes to a separate buffer and reads back, roughly doubling memory traffic for the same number of comparisons.
What is TimSort?
A merge sort that detects runs already in order and merges them, so nearly-sorted input approaches O(n). It is what Arrays.sort uses on object arrays and what Python uses everywhere.