juniorSorting

What is a stable sort and when does stability matter?

Updated Feb 20, 2026

Short answer

A stable sort preserves the relative order of elements that compare equal — if two records share a sort key, the one that appeared first in the input still appears first in the output. It matters whenever you sort by multiple criteria in successive passes, because stability is what lets an earlier sort survive a later one.

Deep explanation

TypeScript
input      (Alice, Sales) (Bob, Eng) (Carol, Sales) (Dave, Eng)
sort by department:
  stable   (Bob, Eng) (Dave, Eng) (Alice, Sales) (Carol, Sales)   <- Bob before Dave, as in the input
  unstable (Dave, Eng) (Bob, Eng) (Carol, Sales) (Alice, Sales)   <- equal keys reordered arbitrarily

Where it actually matters:

  • Multi-key sorting by successive passes. Sort by name, then by department. With a stable sort, records within each department remain name-ordered — you get a two-level sort with two one-line operations. With an unstable sort the first pass is destroyed and you must write a compound comparator instead.
  • User-facing tables. Clicking "sort by date" on a table already sorted by name should leave same-date rows in name order. Unstable sorting makes rows jump unpredictably, which reads as a bug.
  • Reproducibility. A stable sort gives byte-identical output for identical input, which matters for diffable exports, caching, and test assertions.

Which algorithms are stable: mergesort, insertion sort, bubble sort, counting and radix sort (radix sort requires a stable inner sort to work at all). Unstable: quicksort, heapsort, selection sort.

Language defaults are worth knowing. Python's sorted/list.sort (Timsort) and Java's Collections.sort are stable and guaranteed so by their specifications. C's qsort, C++'s std::sort, and JavaScript's Array.sort before ES2019 are not — C++ offers std::stable_sort when you need the guarantee.

The cost is real but modest: stability generally requires O(n) auxiliary space, which is why in-place algorithms tend to be unstable.

Real-world example

Sorting employees by department, then by salary descending within each:

Python
employees.sort(key=lambda e: e.salary, reverse=True)   # secondary key FIRST
employees.sort(key=lambda e: e.department)             # primary key SECOND

Because Python's sort is stable, the second pass groups by department while leaving each group's salary ordering intact. Note the counter-intuitive ordering: you sort by the least significant key first. With an unstable sort this technique is simply unavailable, and you would need key=lambda e: (e.department, -e.salary) instead.

Common mistakes

  • - Assuming every sort is stable. C++'s `std::sort` and pre-2019 JavaScript are not, and code relying on stability breaks silently across languages.
  • - Applying multi-pass sorting in the wrong order — the least significant key must be sorted first.
  • - Believing stability affects correctness of the primary key
  • it only governs ties, but those ties are exactly where the multi-pass technique lives.
  • - Paying for stability where it is irrelevant — sorting primitive integers has no distinguishable equal elements, so an unstable in-place sort is strictly better.
  • - Assuming stability is free
  • it typically needs O(n) auxiliary space, which is why in-place algorithms are usually unstable.

Follow-up questions

  • Why must radix sort use a stable inner sort?
  • Can an unstable sort be made stable?
  • Is Python's sort stable, and is that guaranteed?
  • Why are in-place sorts usually unstable?

More Sorting interview questions

View all →