Sorting stability: what it guarantees and when it matters

What it is

A sort is stable when elements that compare equal keep their relative input order. Python's sorting HOWTO states that its sorts are guaranteed to be stable. MDN notes that since ECMAScript 2019 the specification requires Array.prototype.sort to be stable. Go's sort package documents Stable as keeping the original order of equal elements, separately from Sort, which is not guaranteed to be stable. GNU sort has --stable, which disables its last-resort comparison over the whole line. Stability is a property of the algorithm: merge sort, insertion sort and Timsort are stable; a plain quicksort or heapsort is not.

Why it matters

Stability composes sorts. Sorting by date and then, stably, by status yields rows grouped by status with dates in order inside each group. A sortable table that re-sorts on every click keeps the previous order among ties instead of shuffling them. The opposite case is SQL: ORDER BY on a non-unique column promises nothing about ties, so paginated results can show a row twice or never unless a unique tiebreaker column is appended.

How to apply

• For multi-key sorts prefer one composite key (key=lambda r: (r.status, r.date)): one pass, and the intent is visible. Successive stable sorts from least to most significant key are the alternative when keys need different directions.
• In SQL, end every ORDER BY used for pagination with a unique column (ORDER BY created_at, id).
• Rely on stability only where the documentation states it; look for the word in the library reference before depending on it.
• Python's reverse=True keeps equal elements in their original order, which differs from sorting and then reversing the list.
• On the command line, add -s to GNU sort when ties must keep file order, for example when sorting a log by one field.

Pitfalls

Tests that compare sorted output containing ties depend on both stability and input order; make the expected data tie-free or sort with a full key. Locale collation (LC_ALL) changes the order of the same input between machines, so fix the locale in scripts. Stable algorithms may need extra memory (merge buffers), which matters for very large in-memory arrays. Stability says nothing about the comparison function being consistent: an inconsistent comparator produces undefined order in any algorithm.