On paper mergesort looks strictly better. It is O(n log n) in every case, while quicksort degrades to O(n²) if the pivots go badly. Yet almost every standard library sort is quicksort or a hybrid built on it.
What is the comparison missing?
Accepted Answer
Big O throws away the constant factor, and here the constant factor is the whole story.
Quicksort partitions in place. It walks memory in a straight line, touches each element a couple of times, and needs no extra array. That is close to ideal for a CPU cache.
Mergesort has to merge into somewhere. Either you allocate a second array of size n, or you do an in place merge that is complicated and slow. Either way you are moving more data and your access pattern is worse.
Both are n log n. Quicksort's n log n just has a much smaller number in front of it.
The O(n²) worry is also mostly obsolete, and it matters that you know why rather than trusting it is fine.
Nobody ships naive quicksort. Real implementations pick the pivot as a median of three, or randomise it, which makes the bad case need a deliberately hostile input. Introsort goes further and counts its recursion depth, switching to heapsort if it gets too deep, so the worst case is capped at n log n by construction.
So the textbook comparison is between two algorithms, and the real choice is between one algorithm and a hybrid that was built specifically to remove its weakness.
One thing that keeps mergesort in use though: it is stable, and quicksort is not. If equal elements must keep their original order, the constant factor stops being the deciding argument.
The discussion on each answer is open to members.
Join free to read the rest