What are the real differences between quicksort and mergesort, beyond the textbook bullet points?
The real differences are not in the big-O table. They are in three things. How much memory each one needs. Whether the order of equal items is kept. And how the two behave when the data is already nearly in order.
So let us take them one at a time.
The first difference is the memory. Merge sort splits the list into two halves and then merges them, and the merging needs a second list as big as the original. So merge sort is O of n for the space. Quicksort sorts each half in place, so it only needs a stack, and that is O of log n for the space. So quicksort is the better one when memory is tight.
The second difference is stability, and this is the one that surprises people. Merge sort is stable, so equal items keep their order. A plain quicksort is not stable, so equal items may be put in a different order. If you are sorting people by their score and two people have the same score, then a stable sort keeps them in the order they were given and a plain quicksort does not promise that.
The third difference is how they behave on data that is already nearly in order. Quicksort picks a pivot, and if the pivot is always the smallest value then each split is badly unbalanced. On a list that is already in order, and with a pivot rule that takes the last value, quicksort becomes O of n squared. Merge sort always splits in half, so it stays at O of n log n no matter what the data looks like.
There is a fourth difference that is worth knowing about. Quicksort sorts in place, so it does not need a second copy of the data, and that makes it very cache friendly. Merge sort reads from two places at once, so it makes more trips to the memory. In practice on real machines that difference is small, but it is real.
So the rule to remember is this. Merge sort when you need stability or a guaranteed time, and quicksort when you need low memory or a sort that runs in place.
The last question in this topic shows the stability difference in code.