Stable sorting is sorting that preserves the relative order of elements with equal sort keys. If two records compare as equal and one precedes the other in the input, a stable sorting algorithm keeps them in that order in the output. Stability concerns the treatment of ties, not whether the keys are sorted correctly: both stable and unstable algorithms can produce a correctly sorted sequence.
Definition
Consider an input sequence and a key function . A sort is stable if, whenever
the occurrence originally at position still precedes the occurrence originally at position in the output.
Occurrences matter because two records can have equal keys while carrying different information. For example, sorting these records by score alone:
Input:
(Maya, 80), (Noah, 70), (Lina, 80), (Omar, 70)
Stable output:
(Noah, 70), (Omar, 70), (Maya, 80), (Lina, 80)
Noah remains before Omar, and Maya remains before Lina. An unstable sort is permitted to reverse either pair. It does not necessarily do so on every input; unstable means that preservation is not guaranteed.
Equality under a comparator
When sorting uses a comparison function rather than an explicit key, “equal” means equivalent under that comparison, not necessarily identical as complete objects.
For a strict comparison relation , two elements are equivalent when
Under the usual strict-weak-ordering assumptions, this relation partitions the input into equivalence classes. A stable sort preserves input order within each class.
For example, a case-insensitive string comparison may treat Apple and apple as equivalent even though their character sequences differ. Stability preserves whichever spelling occurred first. An inconsistent comparator can invalidate sorting guarantees; stability does not repair a comparison rule that violates the algorithm’s ordering requirements.
Multiple-key sorting
Stability is especially useful when records must be ordered by several fields. Suppose employees should be ordered primarily by department and secondarily by surname. Two passes can achieve this:
- Sort by surname.
- Stably sort by department.
The second pass groups departments while preserving surname order inside each department. The first pass need not be stable merely to establish surname order; however, if original input order must also be preserved among records equal on both fields, both passes must preserve those ties.
More generally, successive stable sorts are applied from the least significant key to the most significant key. For keys , where has highest priority, sort first by , then by , and continue through .
An alternative is a single comparison using all fields in priority order. These methods produce the same ordering of distinct key combinations. A stable composite-key sort additionally preserves input order among records whose complete key combinations are equivalent.
This principle also underlies least-significant-digit radix sorting: each digit pass must preserve the order established by less significant digits.
Stability of common algorithms
Stability depends on the implementation, not solely on an algorithm’s name. The following classifications describe conventional implementations.
| Algorithm | Usually stable? | Relevant mechanism |
|---|---|---|
| [[insertion-sort | Insertion sort]] | Yes |
| [[merge-sort | Merge sort]] | Yes |
| [[timsort | Timsort]] | Yes |
| [[quicksort | Quicksort]] | No |
| [[heapsort | Heapsort]] | No |
| [[counting-sort | Counting sort]] | Yes, with appropriate placement |
| Radix sort | Depends on the variant | Least-significant-digit sorting requires stable digit passes; other variants need not be stable. |
Maintaining stability during merging
Merge sort illustrates how a local implementation decision establishes stability. Suppose two individually stable, sorted runs come from consecutive portions of the original input. During merging:
- take the smaller front element;
- when the front elements compare as equal, take the element from the left run.
Every element in the left run originally preceded every element in the right run. Choosing from the left on ties therefore preserves their original order. Applied throughout the recursive merge process, this rule produces a stable result.
Choosing the right run first on ties can still produce correctly sorted keys, but breaks stability.
Stable variants of unstable algorithms
Quicksort can be implemented stably, for example by distributing elements into separate less-than, equivalent-to, and greater-than sequences while preserving traversal order within each sequence. Such a version has different storage and performance characteristics from conventional in-place quicksort.
Likewise, the existence of an unstable conventional implementation does not prove that an entire algorithm family cannot be made stable. Stability claims should therefore be attached to a specified algorithm or implementation.
Making an unstable sort preserve ties
An unstable sorting routine can produce a stable result if each element is augmented with its original position. Instead of sorting by key alone, sort by
comparing the original position only when the primary keys are equivalent.
Because original positions distinguish occurrences, the augmented ordering forces equal-key records to remain in input order. This technique is often described as decorating records with their indices, sorting them, and removing the decoration.
Explicitly storing indices typically requires additional storage, though the cost depends on the representation and whether positions are already available. Comparisons also gain a tie-breaking step. The resulting operation is stable with respect to the original keys even if the underlying routine does not itself guarantee stability.
Time and space costs
Stability is distinct from time complexity and space complexity. It does not imply a particular asymptotic running time or storage requirement.
For example:
- Stable insertion sort uses constant auxiliary storage in its conventional array implementation, but has quadratic worst-case running time.
- Conventional array-based merge sort is stable and takes time, while generally requiring auxiliary storage.
- Merge sort on a linked list can merge by relinking nodes rather than copying records into a linear-sized auxiliary array. Control-stack costs depend on the implementation.
- Specialized stable in-place merging and sorting techniques exist, but their implementation complexity and practical costs differ from those of straightforward buffered methods.
Thus, the common association between stability and extra memory reflects widely used implementations rather than a universal requirement.
Applications and limitations
Stable sorting is useful whenever the input order carries information that should survive ties. Examples include preserving arrival order among equal-priority records, retaining a previous sort within newly formed groups, and displaying equal-valued entries without unnecessary rearrangement.
In databases, stability must be distinguished from query-order guarantees. A query using SQL ORDER BY on a nonunique column does not, by itself, guarantee a particular order among tied rows. An explicit additional ordering key is needed when that order matters; relying on an internal sorting implementation is insufficient.
Stability also does not create determinism from an unspecified input order. In parallel computing or distributed computing, a stable sort preserves the order of the sequence it receives, but that sequence may vary between executions. Reproducible tie ordering requires a defined input order or an explicit tie-breaker.
Descending stable sorting still preserves input order among equal keys. Reversing the entire output of an ascending stable sort generally does not: it reverses the equal-key groups as well. A descending comparator used with a stable algorithm preserves ties directly.
Finally, sorting stability is unrelated to numerical stability, which concerns sensitivity to errors in numerical computation. Here, “stable” refers only to preserving the relative order of equivalent elements.