· Development

What is a stable sort? Keeping ties in their original order

What stable sorting means, why it matters when you sort by more than one key, and what the standard sorts in Python, JavaScript, Java and C++ actually guarantee.

DevelopmentAlgorithms

You click the “Date” column in a table, and rows with the same date come out in a different order than before. That is not necessarily a bug. It comes down to whether the sort is stable.

What “stable” means

A sort is stable when elements that compare equal keep their original relative order. The Python documentation puts it as: “when multiple records have the same key, their original order is preserved.”

Take a list of orders sorted by date:

Original position Order Date
1 A Sep 2
2 B Sep 1
3 C Sep 2

After sorting by date, B comes first. With a stable sort, A and C follow in that order, every time. An unstable sort may give C, A instead. Both results are “sorted by date”, so neither is wrong. The unstable one just makes no promise about the order within a tie.

Stability only matters when equal elements can be told apart. In an array of plain integers, two 5s are the same thing. The difference shows up with records or objects that carry more than the sort key.

Why it matters: sorting by several keys

The most practical use of a stable sort is sorting in passes. To sort “by department, then by salary grade within each department”, sort by the secondary key first, then by the primary key. Because the second sort is stable, the order from the first pass survives inside each department.

The Python documentation shows the same technique:

from operator import attrgetter

s = sorted(students, key=attrgetter("age"))            # secondary key: age
s = sorted(s, key=attrgetter("grade"), reverse=True)   # primary key: grade, descending

The same idea is behind table UIs where clicking one column header and then another keeps the first column’s order among ties. With an unstable sort you can’t count on that.

What each language’s standard sort guarantees

What counts is whether the specification or documentation guarantees stability, not whether it usually looks stable. An implementation that happens to be stable can change between versions or environments if the specification doesn’t require it.

Language Function Stable?
Python list.sort(), sorted() Guaranteed: the docs say “guaranteed to be stable”
JavaScript Array.prototype.sort() Required by the specification since ECMAScript 2019 (10th edition), but only with a consistent comparator (see below); earlier editions did not require it
Java Arrays.sort(Object[]), List.sort() Guaranteed: “equal elements will not be reordered”
Java Arrays.sort(int[]) and other primitives Not stated. The implementation is a Dual-Pivot Quicksort, but equal int values can’t be told apart, so it makes no difference
C++ std::sort Not guaranteed: the standard marks only std::stable_sort as stable and makes no such promise for std::sort
C++ std::stable_sort Guaranteed, at the cost of roughly N·log²N comparisons when extra memory isn’t available

Python sorts with Timsort, and the documentation for Java’s List.sort() says its implementation is a stable merge sort adapted from Python’s Timsort.

JavaScript: stable only with a well-behaved comparator

The ECMAScript specification (ECMA-262) requires Array.prototype.sort to be stable only when the comparator is a consistent comparator. Otherwise the sort order is implementation-defined: no promise of stability, and no promise that the result is sorted at all.

A comparator (a, b) => … must return a number, and its sign carries the meaning:

  • negative: a comes before b
  • positive: a comes after b
  • zero: they are equal (a stable sort keeps their original order)

A common mistake is returning a boolean:

players.sort((a, b) => a.score > b.score);   // not a valid comparator
players.sort((a, b) => a.score - b.score);   // valid comparator (ascending)

The specification converts the comparator’s result to a number, so true becomes 1 and false becomes 0. When a.score < b.score the function should return a negative number, but it returns 0, which means “equal”; called with the arguments swapped, it returns 1, which means “not equal”. That is not a consistent comparator, so even if it happens to sort correctly in some engine, the specification gives you nothing to rely on.

With no comparator at all, the default sort converts values to strings and compares those (undefined goes to the end). That is why an array of numbers ends up in dictionary order:

[10, 9, 1].sort();                 // [1, 10, 9]
[10, 9, 1].sort((a, b) => a - b);  // [1, 9, 10]

Not relying on stability

If you have to use an unstable sort, or you don’t want readers of your code to need to know about stability, add a tie-breaking key to the comparison. For example, compare by order ID when the dates are equal. Then every sorting algorithm gives the same single result.

orders.sort((a, b) => a.date.localeCompare(b.date) || a.id - b.id);

In C++, giving std::sort a complete ordering like this makes the result deterministic without std::stable_sort. On the other hand, if the original input order is itself the meaningful tie-breaker and isn’t stored anywhere, a stable sort is the simplest tool.

Specifications and documentation used

Back to the blog