Stable vs Unstable Sorting

By Victor Arce

Two sorts can both put a list in the right order and still disagree about something that matters: what happens to the original index order of equal values. That's stability: a sort is stable if items that tie on the sort key come out in the same order their indices had to begin with.

In the cards below, two share the value 3 — one from index 1, one from index 3. The big number is the value we sort by; the small subscript is the original index. Watch whether index 1 stays ahead of index 3 once their values tie.

What just happened

When two items tie on the sort key, a sort has to put one of them first. A stableStable: equal values keep their original relative order after sorting. sort always keeps the lower original index first — so the 3 from index 1 stays ahead of the 3 from index 3, exactly as in the input. An unstable sort is free to break the tie however its mechanics happen to fall, so it might move the 3 from index 3 ahead of the one from index 1. Both outputs are "sorted" — and if you only look at the values they're identical; the difference is purely in the index order of the equal items.

• Stable:Stable: equal values keep their original relative order after sorting. insertion sort, merge sort, counting sort, bubble sort.
• Unstable: quicksort, heapsort, selection sort (the long-distance swaps jump equal keys past each other).

Why it matters

Stability is what lets you sort by more than one key in simple passes. Say you have a list of orders and you want them grouped by customer, and within each customer by date. Sort by date first, then by customer with a stable sort: the second pass groups customers together while preserving the date order inside each group, because ties (same customer) keep their existing arrangement.

With an unstable sort that trick falls apart — the second pass would scramble the order the first pass established, and you'd have to compare both keys at once. Stable sorting turns a hard multi-key sort into a sequence of easy single-key ones.

Back to Foundations