Stability of Sorting Algorithms

Definition

A sorting algorithm is stable if, for any two elements with equal sort keys, their relative order in the input is preserved in the output. In other words, if $A[i] = A[j]$ and $i < j$, then after sorting, the element originally at $i$ appears before the element originally at $j$.

Stability is about the behaviour with respect to duplicate keys; it says nothing about the algorithm’s running time.

Which Sorts Are Stable

Algorithm	Stable?	Reason
Insertion sort	Yes	Places each element into its correct sorted position without jumping over equal elements
Selection sort	No	Swapping the minimum into position can leap over equal elements, changing their relative order
Mergesort	Yes	Merge takes from the left subarray when keys are equal, preserving input order
Quicksort	No	Partitioning swaps elements arbitrarily; equal keys can cross each other
Heapsort	No	Heap operations (reheapify, extract) do not preserve relative order of equal keys
Counting sort	Yes	Iterates from right to left when placing output, preserving rightmost-later ordering
Radix sort	Depends	Stable if the underlying digit sort is stable (typically counting sort)
Bucket sort	Depends	Stable if the sort used within each bucket is stable and concatenation is ordered

Why Stability Matters

Multi-key Sorting

Suppose we want to sort student records first by exam mark (descending) and then alphabetically by surname for students with the same mark. Using a stable sort:

1. Sort by surname (any sort works for this pass).
2. Stably sort by mark.

After step 2, students with equal marks remain in surname order from step 1. If the mark sort were unstable, the alphabetical ordering could be destroyed.

This technique generalises: to sort by $m$ keys in priority order (least significant first), use $m$ stable sorts. This is sometimes called the “stable sort composition” property.

Radix Sort

Radix sort depends fundamentally on stability. Each digit pass must preserve the ordering established by less significant digits. An unstable digit sort would scramble the work of previous passes, making the algorithm incorrect.

If you only have access to an unstable sort and need stability, you can extend the sort key to include the original index as a tiebreaker: (original_key, original_index). This guarantees uniqueness and simulates stability, at the cost of $\Theta(n)$ extra space for the extended records.

Counterexample: Unstable Quicksort

Given [(3, A), (3, B)] where A and B are the original order:

• Choose pivot = 3 (the last element, (3, B)).
• All other elements are $\le$ pivot, so they land left of pivot.
• The partition may swap (3, A) with itself or rearrange arbitrarily.
• Output might be [(3, B), (3, A)], violating stability.

Summary

Property	Value
Stable sorts	Insertion, Mergesort, Counting sort, (some) Radix
Unstable sorts	Selection, Quicksort, Heapsort
Key uses	Multi-key sorting, radix sort, duplicate-sensitive applications
Emulating stability	Extend key with original index as tiebreaker