Woodstock Blog

a tech blog for general algorithmic interview questions

[Question] Compare Mergesort and Quicksort


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

Typical in-place sort is not stable.


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.


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.


Quicksort is faster.

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