Stable versus Unstable Sorting

A stable sort preserves the original order of equal elements, which matters more than it first appears.

When ties are not really ties

Sorting reorders elements by a key, but two elements can share the same key. A stable sort keeps such equal elements in their original relative order, while an unstable sort may reorder them arbitrarily.

Why stability matters

Stability becomes important when you sort by one field after another.

Sort records by name, then by date. A stable date sort keeps names ordered within each date.
This lets you build multi key orderings by sorting on the least significant key first and the most significant key last.
Without stability, the earlier ordering is lost on ties.

Which sorts are stable

Merge sort and insertion sort are naturally stable.
Quicksort and heapsort are typically unstable because they swap distant elements.
An unstable sort can be made stable by attaching the original index as a tiebreaker, at the cost of extra memory.

A practical signal

If your data carries meaningful secondary order, choose a stable sort or add an explicit tiebreaker so equal keys stay predictable.

Key idea