Stable vs Unstable Sorting

What Does Stability Mean?

A sorting algorithm is stable if elements with equal keys appear in the same relative order in the sorted output as they did in the input.

Input:  [(Alice, 30), (Bob, 25), (Charlie, 30), (Diana, 25)]
        Sort by age ascending.

STABLE output:
  [(Bob, 25), (Diana, 25), (Alice, 30), (Charlie, 30)]
   ↑          ↑            ↑            ↑
   Bob(25) before Diana(25) — original order preserved
   Alice(30) before Charlie(30) — original order preserved

UNSTABLE output (possible):
  [(Diana, 25), (Bob, 25), (Charlie, 30), (Alice, 30)]
   ↑            ↑           ↑             ↑
   Diana now before Bob — original order REVERSED for age=25
   Charlie now before Alice — original order REVERSED for age=30

Stability only matters when equal elements can be distinguished in some way beyond the sort key — by a secondary key, by position in a database, by insertion timestamp, or by any other tie-breaking criterion. If all elements are truly interchangeable, stability is irrelevant.

Why Stability Matters: Multi-Key Sorting

The most important use case for stability is sorting by multiple keys. The technique: sort by secondary key first (stable), then sort by primary key (stable). The secondary-key order is preserved for elements that tie on the primary key.

Records: [("Alice", HR, 60k), ("Bob", IT, 50k), ("Charlie", HR, 50k), ("Diana", IT, 60k)]

GOAL: Sort by department (primary), then by salary within department (secondary).

Step 1: Sort by salary (stable):
  [("Bob", IT, 50k), ("Charlie", HR, 50k), ("Alice", HR, 60k), ("Diana", IT, 60k)]
   Salary order preserved: Bob/Charlie(50k) before Alice/Diana(60k)

Step 2: Sort by department (stable):
  [("Charlie", HR, 50k), ("Alice", HR, 60k), ("Bob", IT, 50k), ("Diana", IT, 60k)]
   HR before IT.
   Within HR: Charlie(50k) before Alice(60k) — salary order preserved from step 1 ✓
   Within IT: Bob(50k) before Diana(60k)     — salary order preserved from step 1 ✓

With UNSTABLE sort in step 2:
  HR employees: could be [("Alice", HR, 60k), ("Charlie", HR, 50k)] — salary order lost!
  IT employees: could be [("Diana", IT, 60k), ("Bob", IT, 50k)]     — salary order lost!

Output (Java):
Charlie(HR,50k), Alice(HR,60k), Bob(IT,50k), Diana(IT,60k)

Which Algorithms Are Stable?

STABLE (equal elements never change relative order):
  Bubble Sort     — swaps only when arr[j] > arr[j+1], never on ==
  Insertion Sort  — shifts only when arr[j] > key, stops on ==
  Merge Sort      — merge uses <=, copies left before right on equal
  TimSort         — built on merge sort; stable by design
  Counting Sort   — fills output back-to-front preserving input order
  Radix Sort      — uses stable sort (counting sort) per digit pass

UNSTABLE (equal elements may change relative order):
  Selection Sort  — long-distance swap can jump over equal elements
  Quick Sort      — partition step can reorder equal elements
  Heap Sort       — heapify and sift-down can reorder equal elements
  Shell Sort      — long-distance swaps similar to selection sort

Why Each Algorithm Is or Is Not Stable

Bubble Sort — Stable

Condition: swap if arr[j] > arr[j+1]   (strictly greater)

Equal elements (arr[j] == arr[j+1]):
  Condition is FALSE → no swap
  Equal elements NEVER move past each other
  → STABLE ✓

If the condition were arr[j] >= arr[j+1]:
  Equal elements would be swapped → UNSTABLE

Insertion Sort — Stable

Condition: shift while arr[j] > key   (strictly greater)

Equal elements (arr[j] == key):
  Condition is FALSE → loop stops
  key is inserted AFTER all equal elements already in sorted prefix
  → STABLE ✓

Merge Sort — Stable

Merge condition: if left[i] <= right[j], copy left[i]

Equal elements (left[i] == right[j]):
  Condition is TRUE → copy from LEFT first
  Left elements appeared BEFORE right elements in the original array
  Left before right = original order preserved
  → STABLE ✓

If the condition were left[i] < right[j]:
  Equal elements: right copied first → original order reversed → UNSTABLE

Selection Sort — Unstable

Proof:
  Input:  [(B,3), (A,3), (C,1)]   sort by number
  Pass 1: minimum is (C,1) at index 2 → swap with (B,3) at index 0
  Result: [(C,1), (A,3), (B,3)]

  B was at index 0 originally. After swap, B is at index 2.
  A was at index 1 originally. A stays at index 1.
  B jumped PAST A without any comparison between them.
  Original order of (B,3) and (A,3): B before A.
  Final order: A before B.
  → UNSTABLE ✗

Root cause: non-adjacent swaps can jump equal elements to new positions.

Quick Sort — Unstable

Proof:
  Input:  [(A,3), (B,3), (C,3)]   all equal, sort by number
  Pivot = (C,3) (last element), Lomuto partition:

  j=0: arr[0]=(A,3) <= (C,3) → i++, swap arr[0] with arr[0] → no change
  j=1: arr[1]=(B,3) <= (C,3) → i++, swap arr[1] with arr[1] → no change
  Place pivot: swap arr[2] with arr[2] → no change

  Here the result happens to be stable — but consider:
  Input: [(B,1), (A,1), (C,2)]   pivot = (C,2)

  j=0: (B,1) <= 2 → i=0, swap arr[0]↔arr[0] → no change
  j=1: (A,1) <= 2 → i=1, swap arr[1]↔arr[1] → no change
  Place pivot at index 2 → [(B,1),(A,1),(C,2)]  stable here

  More revealing:
  Input: [(A,2), (B,1), (C,2)]   pivot = (C,2)
  j=0: (A,2) <= 2 → i=0, swap arr[0]↔arr[0]
  j=1: (B,1) <= 2 → i=1, swap arr[1]↔arr[1]
  Place pivot: swap arr[2]↔arr[2] → [(A,2),(B,1),(C,2)]

  Input: [(C,2), (A,2), (B,1)]   pivot = (B,1)
  j=0: (C,2) > 1 → skip
  j=1: (A,2) > 1 → skip
  Place pivot: swap arr[0]↔arr[2] → [(B,1),(A,2),(C,2)]
  C was at index 0, A at index 1. Now C(2) is at index 2, A(2) at index 1.
  Both have key=2. C now comes AFTER A — reversed from input where C was before A.
  → UNSTABLE ✗

Heap Sort — Unstable

Heap sort builds a max-heap, then repeatedly extracts the maximum.
During heapify, the sift-down process compares children and swaps the
larger child upward. Two equal elements may be in parent-child relationship,
and sift-down may swap them — reordering equal elements.

Proof:
  Input: [(A,5), (B,5), (C,3)]   sort by number descending then ascending
  Build max-heap: (A,5) may go to root, (B,5) as child — or vice versa.
  Extraction order depends on heap structure, not insertion order.
  → UNSTABLE ✗

How to Make Any Sort Stable

Method 1: Compound Sort Key (Add Original Index)

Extend the comparison key to include the element's original index as a tiebreaker. Elements with equal primary keys are then ordered by index — which preserves the original order.

Output (Java):
Stable result: 1(idx1) 1(idx3) 2(idx6) 3(idx0) 4(idx2) 5(idx4) 5(idx8) 6(idx7) 9(idx5)

Method 2: Use a Stable Sort Directly

The cleanest approach: just use a sort that is already stable.

Language          Stable sort to use
──────────────────────────────────────────────────────────────────────
Java (objects)    Collections.sort(), List.sort(), Arrays.sort(Object[])
                  → all use TimSort — STABLE
Java (primitives) Arrays.sort(int[]) uses Dual-Pivot QuickSort — NOT STABLE
                  → if stability needed, use Integer[] and Arrays.sort(Integer[])

Python            list.sort() and sorted() → TimSort — STABLE (always)

C++               std::stable_sort() → guaranteed stable
                  std::sort() → NOT guaranteed stable (use stable_sort when needed)

JavaScript        Array.prototype.sort → STABLE since ECMAScript 2019
                  (V8 ≥ 7.0, SpiderMonkey always stable, before ES2019 not guaranteed)

How to Test Stability

Stability test:
1. Create an array of objects where multiple elements share the same sort key
2. Record the original positions of equal-key elements
3. Sort with the algorithm under test
4. Check: do equal-key elements appear in their original relative order?

Test case:
  Input: [(B,1), (A,1), (D,2), (C,1)]   sort by number
  Equal-key elements (key=1): B at idx 0, A at idx 1, C at idx 3
  Expected stable output: B before A before C   (original order 0,1,3)

  Stable result:   [(B,1),(A,1),(C,1),(D,2)] ✓
  Unstable result: [(A,1),(C,1),(B,1),(D,2)] ← B jumped to index 2, after A and C

Stability in Real-World Scenarios

1. Database query results
   SELECT * FROM orders ORDER BY customer_id
   Then additionally sort by date — stable sort preserves customer_id
   ordering within the same date.

2. Spreadsheet column sorting
   User sorts by "Region" column. Then sorts by "Revenue" column.
   Stable sort: within each revenue value, regions stay in alphabetical
   order from the previous sort.
   Unstable sort: alphabetical region order is destroyed on the second sort.

3. Version control file listing
   Files listed alphabetically, then sorted by modification date.
   Stable: files modified on the same date remain alphabetical.
   Unstable: same-date files appear in random order.

4. Leaderboard with ties
   Players sorted by score. Ties broken by join date (earlier = higher rank).
   Two-pass stable sort: sort by join date first, then by score.
   Stable: tied-score players appear in join-date order.
   Unstable: tie-breaking is lost.

5. Counting sort and Radix sort
   Radix sort processes digit by digit — it MUST use a stable sort
   for each digit pass. If the digit-level sort is unstable, the
   ordering from previous passes is destroyed. This is why counting sort
   (which is naturally stable when implemented correctly) is used.

Stability Across Languages

Java:
  Arrays.sort(Object[])     → TimSort    → STABLE ✓
  Arrays.sort(int[])        → DualPivotQS → NOT STABLE ✗
  Collections.sort(List)    → TimSort    → STABLE ✓
  List.sort(comparator)     → TimSort    → STABLE ✓

  To sort int[] stably: convert to Integer[] first:
    Integer[] boxed = Arrays.stream(arr).boxed().toArray(Integer[]::new);
    Arrays.sort(boxed, comparator);

Python:
  list.sort()   → TimSort → STABLE ✓ (since Python 2.2, always)
  sorted()      → TimSort → STABLE ✓

C++:
  std::sort          → IntroSort      → NOT GUARANTEED STABLE ✗
  std::stable_sort   → MergeSort      → STABLE ✓
  std::sort with full compound comparator → effectively stable

JavaScript:
  Array.prototype.sort → TimSort in V8 → STABLE ✓ (since ES2019)
  Before ES2019: V8 used unstable sort for arrays > 10 elements.
  Node.js ≥ 11 (V8 7.0+): stable.
  Chrome ≥ 70: stable.
  All modern browsers: stable.

Summary Table

Common Mistakes

Using Arrays.sort(int[]) expecting stability in Java. Primitive array sort uses Dual-Pivot QuickSort — unstable. If you are sorting int[] values that correspond to records and stability matters, box them to Integer[] first, then sort with a comparator.

Assuming JavaScript's Array.sort() is always stable in legacy environments. Before ECMAScript 2019, V8 (used in Node.js and Chrome) used an unstable insertion sort for short arrays (≤ 10 elements) and an unstable QuickSort for longer arrays. Code running on older browsers or older Node.js versions cannot rely on sort() being stable. Check your target environment or add an index tiebreaker.

Using < instead of <= in a custom merge implementation. The stability of merge sort depends entirely on this one character. if (left[i] < right[j]) takes the right element first on ties — reversing equal elements. Always use <= (left before right on ties) in a stable merge.

Not recognising that two-pass sorting requires a stable intermediate sort. The technique "sort by secondary key, then sort by primary key" only works if the second sort is stable. If the second sort is unstable, the secondary-key ordering for equal primary-key elements is lost. The second sort must be stable.

Interview Questions

Q: What is the difference between a stable and an unstable sort, and name two of each?

A stable sort preserves the original relative order of equal-key elements. An unstable sort may reorder them. Stable: Merge Sort, Insertion Sort, TimSort, Bubble Sort. Unstable: Quick Sort, Selection Sort, Heap Sort.

Q: Why does it matter whether a sort is stable when sorting database records?

Database applications frequently sort by one column and then by another. If the second sort is unstable, the ordering from the first sort is destroyed for equal primary-key values. For example: sort employees by name (stable), then sort by department (unstable). The result may interleave employees with the same department in random order rather than alphabetical name order within each department.

Q: How does the two-pass stable sort work and why does it require stability?

To sort by (department, salary): first sort by salary (secondary key, stable), then sort by department (primary key, must be stable). After step 2, equal-department employees are in the order established by step 1 (salary order). If step 2 were unstable, equal-department employees could appear in any order — the salary ordering would be lost.

Summary

Stability means equal elements keep their original relative order after sorting. This matters whenever equal elements are distinguishable — by a secondary key, position, timestamp, or other criterion.

Stable sorts: Bubble Sort (never swap on equal), Insertion Sort (never shift on equal), Merge Sort (<= in merge copies left first), TimSort (built on merge sort), Counting Sort, Radix Sort.

Unstable sorts: Selection Sort (long-distance swap skips equal elements), Quick Sort (partition reorders equal elements), Heap Sort (heapify reorders equal elements).

Language defaults:

• ›Python list.sort() / sorted() → always stable (TimSort since Python 2.2)
• ›Java Arrays.sort(Object[]), Collections.sort() → stable (TimSort)
• ›Java Arrays.sort(int[]) → NOT stable (Dual-Pivot QuickSort)
• ›C++ std::sort → NOT guaranteed stable; std::stable_sort → stable
• ›JavaScript Array.sort() → stable (ECMAScript 2019+, modern V8/SpiderMonkey)

Two-pass multi-key sort: sort by secondary key first (stable), then by primary key (stable). Works because the second sort preserves the first sort's ordering within equal primary keys.

Making any sort stable: add the original index as a tiebreaker in the comparator — compare(a, b) = primaryKey(a) - primaryKey(b) || originalIndex(a) - originalIndex(b).

In the next topic, you will explore Sorting Comparison — a comprehensive side-by-side analysis of all sorting algorithms with benchmarks, use-case guidance, and the definitive decision framework.