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.
| Aspect | Stable sorting | Unstable sorting |
|---|---|---|
| Equal-key relative order | Preserves input order | No preservation guarantee |
| One order-preserving example | Consistent with contract | Possible but not proof of a guarantee |
| Unique business order | Still needs input or tie-key definition | Define 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.
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.