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 |