A stable sort preserves the original relative order of equal keys — an extra guarantee required when sorting by secondary fields or compound criteria.
A sorting algorithm is stable when equal keys keep their original relative order. Stability is not part of the basic sorting contract, because an unstable output may still be ordered and may still be a permutation of the input. Stability is an additional semantic guarantee about records, identities, and secondary fields.
Problem
You have records with keys, and two records may have equal keys but different attached data. You want to sort by key without changing the order of records that compare equal.
Solution
Use a stable sorting algorithm, or modify the comparison key so that equal keys are broken by original position.
For records:
[(key=2, id=A), (key=1, id=B), (key=2, id=C)]A stable sort by key gives:
[(key=1, id=B), (key=2, id=A), (key=2, id=C)]The two records with key 2 remain in the order A, C.
An unstable sort may produce:
[(key=1, id=B), (key=2, id=C), (key=2, id=A)]This is ordered by key, but it does not preserve the original order of equal-key records.
Stability Contract
Let the input array be:
A[0..n-1]Let key(x) be the value used for comparison. A sort is stable if, for any two input positions i and j:
i < j and key(A[i]) = key(A[j])then in the output, A[i] appears before A[j].
This condition refers to element identity, not only element value. If two records have the same key but different payloads, stability controls their relative order.
Why Stability Matters
Stability matters when sorting records in multiple passes. Suppose you have records with department and salary, and you want the final order to be by department first and salary second.
A common stable-sort pattern is:
stable_sort(records, by salary)
stable_sort(records, by department)The second sort groups records by department. Within each department, the first sort’s salary order remains intact because the second sort is stable.
This works only if the second sort preserves equal-key order.
Common Stable Algorithms
Merge sort is stable when the merge step takes from the left side on equal keys.
Insertion sort is stable when it shifts only elements strictly greater than the key.
Counting sort is stable when it places elements by scanning the input from right to left.
Radix sort depends on stable digit sorting. Without stability, least-significant-digit radix sort fails.
Common Unstable Algorithms
Selection sort is usually unstable because it swaps a later minimum element with an earlier element.
Quick sort is usually unstable because partitioning swaps records across the array.
Heap sort is unstable because heap construction and extraction move equal records without preserving their original order.
These algorithms can sometimes be modified to preserve stability, but the modifications usually require extra memory, extra movement, or more complex bookkeeping.
Making an Unstable Sort Stable
One general method is to decorate each record with its original index:
decorated[i] = (key(A[i]), i, A[i])Then sort by (key, original_index).
After sorting, remove the decoration:
A_sorted = [record for (_, _, record) in decorated]This forces equal keys to appear in original order, even if the underlying sort itself is unstable.
The cost is extra memory and a larger comparison key.
Correctness
The decorated-key method is correct because it creates a total order that refines the desired stable order.
For two elements A[i] and A[j] with equal keys and i < j, their decorated keys are:
(key(A[i]), i)
(key(A[j]), j)Since i < j, the first decorated key is smaller. Therefore any correct sort by decorated key places A[i] before A[j].
For elements with different keys, the original key decides the order. Thus the final output is sorted by key and stable among equal keys.
Complexity
Stability does not have a single complexity cost. It depends on the algorithm.
Stable merge sort:
time: O(n log n)
space: O(n)Stable insertion sort:
time: O(n^2)
space: O(1)Stable counting sort:
time: O(n + k)
space: O(n + k)Decorating with original indices usually adds:
space: O(n)and increases comparison cost because each comparison may inspect both the key and the original index.
Implementation Notes
Use a stable sort when record order carries meaning beyond the primary key. This is common in database rows, log records, UI tables, search results, and multi-key sorting pipelines.
Use unstable sorting when only the final key order matters and performance or memory pressure is more important than preserving equal-key order.
When designing a sorting API, document stability explicitly. Users should not infer stability from sorted output alone.
Common Bugs
A frequent bug is assuming that “sorted” implies “stable”. It does not.
Another bug is using >= instead of > in insertion sort. That reverses equal keys and breaks stability.
A third bug is using < instead of <= in merge sort’s merge step. When keys are equal, choosing from the right half first can reverse equal records across halves.
A fourth bug is running multi-pass sorting with an unstable second pass. The earlier ordering is lost.
Takeaway
Stable sorting preserves the order of records with equal keys. It is essential for multi-key sorting and for data where equal keys still carry distinct identities.