Short answer
MergeSort is stable and always guarantees O(N log N), but uses O(N) extra memory. QuickSort sorts in place with O(1) auxiliary space and is faster in practice, but is unstable and has an O(N^2) worst case. However, QuickSort also needs O(log N) extra memory for recursive call frames if it recurses on the smaller partition first; otherwise, it can use O(N) in the worst case.
Explanation
A stable sort preserves the relative order of elements with equal values, which matters when applying multiple sorts (for example, sorting students by name and then by grade). In QuickSort, consistently choosing a poor pivot, such as the first element in an already sorted array, degrades partitioning to O(N^2). Modern algorithms address this with randomized QuickSort or the hybrid IntroSort used by C++ std::sort.
Code example
import random
def merge_sort(a): # stable, always O(n log n), O(n) extra memory
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps equal items in their original order
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
def quick_sort(a, lo=0, hi=None): # in place, O(log n) stack on average, not stable
hi = len(a) - 1 if hi is None else hi
if lo >= hi:
return
pivot = a[random.randint(lo, hi)] # random pivot avoids the O(n²) sorted-input case
i, j = lo, hi
while i <= j:
while a[i] < pivot: i += 1
while a[j] > pivot: j -= 1
if i <= j:
a[i], a[j] = a[j], a[i]
i += 1; j -= 1
quick_sort(a, lo, j)
quick_sort(a, i, hi)Common mistakes
- Using classic QuickSort without random pivot selection on partially sorted data, causing severe slowdowns.