Algorithms & Data Structures • Sensei Learning System

Stable vs Unstable Sorting: Why Equal Items Keep Their Order

Two lists can be sorted the same way by value and still disagree on who stands next to whom. The difference is stability — and it is decided in the tie case.

Core Concept

A stable sort preserves the input order inside every equal-key group. If two records have the same key, the one that appeared first in the input also appears first in the output. Stability is a promise about ties only — for different keys, any correct sort may freely order them. Quicksort and heapsort typically break the promise; merge, insertion, counting, and radix sorts keep it when their tie case is written correctly.

Key Components

1. The Tie Group

All records sharing one key. Stability has nothing to say about records with different keys — only about who keeps their place inside a group of equals.

2. The Implementation Tie-Break

Merge sort is stable only if its tie case takes the left item first. Insertion sort stays stable if it never moves an item past an equal key. Quicksort/heap need extra machinery.

3. The Reverse-Pass Rule

To order by state then city, sort by the secondary key (city) first, then the primary key (state). The final stable pass preserves city order inside each state.

4. The Falsification Test

Tag each record with its unique input index, create repeated keys, sort, then compare index order inside each tie group. Any reversal proves the sort is not stable.

How It Works

Start with tied keys. Here B and D both carry 35, so any sort by age must decide their relative order.

Before — input order

A·40 B·35 C·20 D·35 E·50

↓

After — stable sort by age

C·20 B·35 D·35 A·40 E·50

B remains before D because their keys tie and the input had B first. An unstable sort might emit D before B — still sorted, still “correct” — and downstream code that assumed input order silently breaks.

Stack keys in reverse. For “state, then city” the execution order is the reverse of the reading order: stable sort by city first, then stable sort by state.

The last pass wins. Each stable pass fixes the order of ties on its own key, and a later stable pass leaves those resolved ties untouched — so city order survives inside every state group.

Real-World Applications

Multi-key ordering in SQL and dataframesORDER BY dept, title, tenure — stability (or the reverse-pass rule) is what makes the chained keys compose.
Python's sorted() is stable (Timsort)The classic idiom: sort once by the secondary key, then by the primary, and let stability carry the rest.
External and external-merge sortingDatabases and big-data engines merge sorted runs; a stable merge keeps original-record order when run keys collide.
Event and audit log re-sortingRe-grouping records by a coarser key while preserving capture order inside each group, so downstream dedup sees a deterministic sequence.

Checkpoint — Answer Before You Move On

1After the stable sort by age, why does B·35 still precede D·35 — and exactly what does stability guarantee that it does not guarantee? It constrains only the order inside a tie group, never the order of different keys.

2You need the final list ordered by state, then city. Which key do you sort by first, and why does that order of passes produce the right result? Read order is state·city; execution order is the reverse. The last stable pass decides the order of ties on its key.

3Why can a test where every key is distinct never detect an unstable sort — and what must you add to the test to make stability measurable? No tie group exists, so there is nothing for stability to violate. Repeated keys plus unique input-index tags.