Quicksort

Quicksort is faster because it’s in-place sort (with O(log n) stack space).

Typical in-place sort is not stable.

Mergesort

Mergesort uses O(n) space, thus slower.

It is stable sort.

Stability 稳定排序

When sorting, if only part of the data is examined, there’re possibility of multiple different correctly sorted versions of the original list. Stable sorting algorithms will preserve the original relative order.

One application for stable sorting algorithms is sorting a list using a primary and secondary key.

Example:

Stable sort: first sorting by rank/number (using any sort), and then a stable sort by suit.

Quicksort would not be able to do that.

Conclusion

Quicksort is faster.

Best Average Worst Memory Stability
Quicksort nlgn nlgn n^2 lgn average
n worst case
Not
Merge sort nlgn nlgn nlgn n worst case Yes