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