Comparisons and explanations · Intermediate

Stable versus unstable sorting

Track equal-key records to distinguish sorting stability, multi-key ordering, deterministic output and implementation costs.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Stability concerns relative order among equal keys
  2. Trace tied score records
  3. Apply lower-priority keys before higher-priority keys
  4. Read the implementation contract, not only the name
  5. Define tie meaning when reproducibility matters
  6. Ask Logeia about this articleCheck your understanding

Stability concerns relative order among equal keys

A stable sort preserves the input-relative order of elements whose comparison keys are equal. Stable does not mean constant running time, immunity from failure or universally high speed. An unstable sort lacks the relative-order guarantee; it does not necessarily reverse every tie or produce a different result on every run. One example retaining the original order is therefore not proof that the implementation is stable. Equality for this purpose comes from the key and comparison contract. Two records can contain different identifiers and payloads yet still count as tied because the selected sorting key is equal. Specify that key before interpreting stability or deciding what output ordering the application requires.

AspectStable sortingUnstable sorting
Equal-key relative orderPreserves input orderNo preservation guarantee
One order-preserving exampleConsistent with contractPossible but not proof of a guarantee
Unique business orderStill needs input or tie-key definitionDefine explicit secondary keys

Trace tied score records

Take input (A,80), (B,70), (C,80) and sort by increasing score. A stable result places B first, followed by A then C. An unstable method may allow B,C,A, but it can also happen to return B,A,C on that input. Both sequences have correctly ordered scores. Key ordering and preservation of tied records are separate properties. Stability is useful if arrival order carries meaning, such as registration sequence. If the input order itself is unspecified because of concurrent collection, a stable sort alone does not create a unique business-defined order. The application may need an explicit secondary key rather than relying on whichever tied order happened to reach the sorting function.

Python
records = [('A', 80), ('B', 70), ('C', 80)]
result = sorted(records, key=lambda item: item[1])
assert [name for name, score in result] == ['B', 'A', 'C']

Apply lower-priority keys before higher-priority keys

To order primarily by assignee and secondarily by date, first sort by date and then stably sort by assignee. Within each assignee group, the earlier date order remains. Reversing these passes can instead make date the primary key. Comparing a tuple of keys in one pass is another approach. In either case, define ascending or descending direction, missing values and text normalization as needed. Stability does not make every sequence of sorting passes equivalent. A later pass takes precedence, preserving previous order only among its ties. Trace actual records to verify that the intended key hierarchy matches the chosen pass order or composite-key comparison.

Read the implementation contract, not only the name

A standard stable merge chooses the left run’s item first when keys tie, preserving relative order. Typical in-place quicksort does not promise stability, although stable variants can be designed. Consult the actual library contract rather than inferring everything from an algorithm-family name. Python’s sort and sorted provide a concrete stability guarantee. Memory bounds, comparison counts and stability remain separate properties, so check each required one. An inconsistent comparator can undermine the sorting assumptions regardless of stability. Validate how the key and ordering behave, especially for special numeric values or custom objects, instead of attributing every surprising output to the choice between stable and unstable sorting.

Define tie meaning when reproducibility matters

For reproducible reports or pagination, define what should take precedence among records tied on a primary key. A timestamp alone can tie; an identifier or another explicit secondary key may be needed. SQL ordering by only some columns likewise does not automatically supply the desired order for all ties. Selecting a stable function and defining a business ordering are separate responsibilities. Tests should check overall key order and the identifier order inside equal-key groups separately. A coincidentally repeated output is weaker evidence than an explicit contract covering input order and tie-breaking. This distinction helps explain when stability is sufficient and when a complete composite ordering is the actual requirement.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path