Stable vs Unstable Sorting Algorithms

What Is Sorting Stability?

A sorting algorithm is stable if it preserves the relative order of elements with equal keys. In other words, if two elements have the same sort key, they appear in the output in the same order as they appeared in the input.

Visual Example

Sorting students by grade (ignoring name order):

Input	Name	Grade
1	Alice	B
2	Bob	A
3	Carol	B
4	Dave	A

Stable sort by grade: Bob(A), Dave(A), Alice(B), Carol(B) — original order preserved within each grade.

Unstable sort might produce: Dave(A), Bob(A), Carol(B), Alice(B) — relative order within grades changed.

Which Algorithms Are Stable?

Stable	Unstable
Merge Sort	Quick Sort
Insertion Sort	Heap Sort
Bubble Sort	Selection Sort
Counting Sort	Shell Sort
Radix Sort	Introsort
Timsort

Why Stability Matters

1. Multi-key sorting: Sort by last name, then stable-sort by department. The result is sorted by department with names in order within each department.

2. Database operations: SQL ORDER BY department, name relies on stable sorting to produce consistent results.

3. User interface: When a user clicks a table column header to sort, previously sorted columns should maintain their order for equal values.

4. Reproducibility: Stable sorts produce deterministic output, which is important for testing and debugging.

Can Unstable Algorithms Be Made Stable?

Yes, by appending the original index as a secondary key. But this increases space usage by O(n) and adds overhead to comparisons. In practice, it is usually better to choose a naturally stable algorithm when stability is required.

Java and Python's Choice

Both Java (Arrays.sort for objects) and Python (list.sort) use Timsort, a stable O(n log n) algorithm, because stability is almost always desirable when sorting objects. Java uses dual-pivot quicksort for primitives, where stability is irrelevant since equal primitives are indistinguishable.