What is "Stability"?
A stable sort preserves the relative order of elements that compare as equal. An unstable sort may reorder them arbitrarily.
This sounds academic until you hit a real scenario:
Example: You have a list of employees, each with a name and a department. You first sort by department, then sort by name.
- Stable sort: Within each name group, employees remain sorted by department (the previous sort's order is preserved).
- Unstable sort: The department ordering within name groups is scrambled. You lose information from the first sort.
Stability matters whenever you sort by multiple criteria sequentially, or when the original order of equal elements carries meaning (e.g., timestamps, insertion order).
Quick Sort is unstable. Merge Sort is stable. Timsort is stable.
The Quick Sort Killer: Already-Sorted Input
Why does Quick Sort degrade to O(N²)?
If you always pick the first element as the pivot, and the array is already sorted:
[1, 2, 3, 4, 5] pivot = 1
→ [] and [2, 3, 4, 5] (split: 0 elements left, 4 right)
→ pivot = 2
→ [] and [3, 4, 5] (split: 0 elements left, 3 right)
Every partition produces one empty side and one side with N-1 elements. Instead of halving the problem, you reduce it by one element per step — exactly like Linear Search. You make N partitions of decreasing size: N + (N-1) + (N-2) + ... + 1 = O(N²).
The fix: Use a randomized pivot (pick a random index) or the median-of-three strategy (pick the median of the first, middle, and last elements). This makes the O(N²) case astronomically unlikely in practice.