Stable Sort: The Property That Makes Multi-Key Sorting Actually Work

You sort a table of employees by department. Then you sort it by salary. You expect employees with the same salary to end up grouped by department. Some are. Some are quietly in the wrong order, and the result passes visual inspection.

That's a stability bug. A stable sort would have prevented it. It doesn't crash. It's just silently wrong, like a coworker who nods and then does something completely different.

Stability Is About the Tie

A sorting algorithm is stable if it preserves the original relative order of elements that compare as equal.

If Alice and Bob both have salary $80,000 and Alice appeared before Bob in the input, a stable sort guarantees Alice still appears before Bob in the output. An unstable sort makes no such promise. The output is correctly sorted by key, but the relative order of tied elements is undefined. Your sort passed. Your data is wrong. Congrats.

Stability only matters when two elements share the same key. When all keys are distinct, every correct sort produces identical output and the question is irrelevant. Things get interesting at the tie.

Two outputs side by side. Left: STABLE sort keeps Alice before Bob among $80k entries. Right: UNSTABLE sort flips them. Both outputs sort correctly by salary.

Both outputs are sorted by salary. The bug is invisible until you look at secondary order.

Multi-Key Sorting Is Where Stability Pays Off

There are two ways to sort by multiple keys simultaneously. First: write a single comparator that considers all keys in priority order. Second: sort by the least important key first, then by the next key, and so on up the priority chain.

Option two is the practical choice. It's modular. You write one simple sort per key and compose them. Each pass does one thing.

But it only works if every sort pass is stable. When you sort by department after sorting by salary, the department sort must leave the salary ordering intact inside each department group. If the department sort is unstable, it scrambles the salary ordering, and the first pass accomplished nothing. You spent compute rearranging the array in a way that the second sort immediately destroyed.

records = [
    ("Alice", "Engineering", 95000),
    ("Bob",   "Marketing",   80000),
    ("Carol", "Engineering", 80000),
    ("Dave",  "Marketing",   95000),
]

# Sort by salary first, then by department.
# The second sort must be stable to preserve salary order
# within each department group.
by_salary = sorted(records, key=lambda r: r[2])
by_dept   = sorted(by_salary, key=lambda r: r[1])

# With a stable sort:
# Engineering: Carol (80k), Alice (95k)  <- salary order intact
# Marketing:   Bob (80k),   Dave (95k)   <- salary order intact

Python's sorted() is stable, so this works. With an unstable sort, Alice might appear before Carol inside Engineering because Alice came first in the original input, not because of salary. The first sort is silently undone. Your two-pass sort is now a one-pass sort that forgot to tell you.

This exact mechanism is why LSD radix sort works. You sort by the ones digit, then the tens digit, then the hundreds digit. Each digit pass must preserve the ordering from previous passes. Sedgewick's analysis at Princeton makes this explicit: "Radix sort is a stable sort, so that each pass preserves the sorted result from the previous pass." Every standard implementation uses counting sort as its subroutine because counting sort is stable.

UI tables follow the same pattern. A user sorts by column B, then by column A, and expects rows with matching column-A values to stay in column-B order. Multi-key sorting under a different name. Your users will notice before your tests do.

Which Sorting Algorithms Are Stable?

Insertion sort is stable because it only shifts an element leftward past things strictly smaller than itself. It never steps over an equal element. Two equal elements arriving from the right end up adjacent in their original order, with nothing to disturb them.

Merge sort is stable if you implement the merge step correctly. When the front elements of the left and right subarrays are equal, always take from the left. That is the entire source of merge sort's stability. One comparison operator. One character difference between stable and unstable (< vs <=).

Merge step showing a tie. Left subarray holds (5,'a') at the front, right holds (5,'b'). Rule: take from left. Output gets (5,'a') before (5,'b'), preserving original order.

Write < instead of <= in the merge comparison and you silently reverse the relative order of every tied pair. The sort is still "correct." The stability is gone.

Why does left-before-right work? The left subarray contains elements that appeared earlier in the original input. Preferring the left on a tie keeps earlier input elements earlier in the output. That is the stability invariant.

Counting sort is stable, but only with one specific implementation choice: fill the output array right to left. The algorithm builds prefix sums to find each element's last output slot. Iterating the input in reverse, you place the current element at that slot and decrement. The rightmost occurrence of a key gets the rightmost available slot. Work backward through all equal elements and they land in their original input order in the output. Fill left to right instead and the relative order inverts. The counting sort algorithm post traces this step by step.

Timsort is a merge-insertion hybrid used by Python's sorted(), Java's Arrays.sort(Object[]), and JavaScript's Array.sort() (ECMAScript 2019 onward). It's stable because it's fundamentally a merge sort and inherits the left-before-right tiebreak rule.

Bubble sort is stable for the same reason as insertion sort. It swaps adjacent elements only when the left is strictly greater than the right. Equal adjacent elements never swap.

Unstable Sorts and the Swap That Breaks Them

Selection sort is the most teachable counterexample. It scans the unsorted portion, finds the minimum, and swaps it directly into position. That long-range swap is the problem.

Consider: [(3,'a'), (3,'b'), (1,'c')]. Sort by number.

The minimum is (1,'c') at index 2. Swap with index 0.

Result: [(1,'c'), (3,'b'), (3,'a')].

The two 3s are now in the wrong relative order. (3,'b') appears before (3,'a'), but in the original input 'a' came first. One long-distance swap and stability is dead. Selection sort does this on every iteration and never thinks about it.

Selection sort step: (1,'c') at index 2 swaps with (3,'a') at index 0. Result shows (3,'b') now before (3,'a'). Relative order reversed.

It's sorted. It's also broken. Neither fact is obvious from looking at the numbers.

Quicksort is unstable because the partition step swaps non-adjacent elements with no regard for original position. Elements equal to the pivot land wherever the partition logic puts them. Equal elements on opposite sides of the pivot can arrive in any order.

Heapsort is unstable for a structural reason. Building the heap reorders the entire input array into a tree shape. That reordering alone can scramble equal elements. The subsequent sift-down operations move elements in large jumps that bear no relationship to original index. Heapsort genuinely does not know or care where things came from.

Both quicksort and heapsort trade stability for speed. Quicksort's in-place partition avoids O(n) auxiliary memory. Heapsort achieves O(n log n) worst case with O(1) space. These are real tradeoffs, not oversights. Use them when keys are distinct or when downstream logic has no secondary ordering requirement. The merge sort vs quicksort analysis covers the full performance picture.

What Your Language Actually Gives You

Language	Default sort	Stable?
Python `sorted()` / `.sort()`	Powersort (Timsort before 3.11)	Yes
Java `Arrays.sort(Object[])`	Timsort	Yes
Java `Arrays.sort(int[])`	Dual-pivot quicksort	No
JavaScript `Array.sort()`	Timsort (ECMAScript 2019+)	Yes
C++ `std::sort`	Introsort	No
C++ `std::stable_sort`	Merge sort variant	Yes
Rust `slice::sort()`	Timsort-derived	Yes
Rust `slice::sort_unstable()`	Pattern-defeating quicksort	No

The Java primitive case catches everyone at least once. Arrays.sort(int[]) uses dual-pivot quicksort, which is faster in practice. Arrays.sort(Integer[]) uses Timsort and is stable. Same method name. Different algorithm. Different stability guarantee. Different bug waiting for you at 11pm.

The rationale makes sense once you hear it: two identical int values are completely indistinguishable, so instability has no observable effect. Two Person objects with the same salary might have different names, so stability matters. The JDK is right. You just have to know the rule.

JavaScript's history is worth a moment. Before ECMAScript 2019, the spec left sort stability to the engine. V8 used an unstable algorithm for arrays larger than 10 elements. Chrome 70 switched to Timsort, and the spec was updated to require stability. Code that depended on undefined behavior silently changed semantics across browser versions. If you ever saw a sort that worked fine in Firefox but not Chrome, this might be why.

Any Sort Can Be Made Stable

If you need stability from an algorithm that doesn't provide it, decorate each element with its original index as a tiebreaker:

def force_stable(items, key):
    # No two elements share the same index, so equal keys never truly tie.
    decorated = [(key(item), i, item) for i, item in enumerate(items)]
    decorated.sort()
    return [item for _, _, item in decorated]

Since no two elements share the same original index, equal keys never actually tie in the decorated comparison. The tie breaks on the index, and earlier indices win. This is the decorate-sort-undecorate pattern, also called the Schwartzian transform in Perl. It costs O(n) extra space for the tuples, but it works with any sort algorithm in any language. Wrap your unstable sort in this and nobody has to know.

In Python this is unnecessary since sorted() is already stable. But if you're wrapping a C extension or working in a language with no stable built-in, this is the universal fix.

The Trap Nobody Warns You About

Instability is invisible when no two keys are equal. A correctly written unstable sort on a dataset with all-distinct keys produces identical output to a stable sort. Tests pass. Code ships. The bug waits for real data.

This is why stability bugs are hard to catch. They appear when two employees share a salary tier, when a leaderboard has tied scores, when API responses carry timestamps that repeat within a second. Development datasets are often too clean. You generate 10 records with distinct keys, the tests pass, and you go home thinking the sort is fine.

When you write sort-dependent logic, ask two questions. Can any two inputs share the same key? If yes, does downstream logic assume any secondary ordering? Both true means you need either a stable sort or an explicit composite comparator.

An interview question that probes this is worth practicing out loud. You get to demonstrate that you've thought about data, not just algorithms. SpaceComplexity runs voice-based DSA mock interviews with rubric feedback, and sort stability is exactly the kind of edge-case reasoning that separates a strong hire from a borderline one.

Quick Recap

A sort is stable when equal-key elements come out in the same relative order they went in.
It only matters when keys repeat and downstream logic cares about secondary ordering.
Stable: insertion sort, merge sort (left-before-right on ties), counting sort (right-to-left fill), bubble sort, Timsort.
Unstable: selection sort (long-range swap), quicksort (partition ignores original order), heapsort (heap shape scrambles order).
Python is stable by default. Java is stable for object arrays, unstable for primitive arrays. C++ std::sort is unstable; std::stable_sort is not. Rust has both.
Universal fix: decorate with (key, original_index) to force any sort to behave stably.