# When does an unstable sort reorder equal elements and break downstream assumptions?

**Date of Record:** 2026 November 2

**Scope:** Applies to sorts and priority orderings where readers depend on the relative order of equal-key elements, when the sort implementation is not guaranteed stable. Excludes sorts with an explicit tiebreaker, and sorting primitives where equal elements are indistinguishable.

## Core Distinction

**Predicate.** An ordering over equal keys is deterministic if and only if the sort is stable *or* a tiebreaker makes all keys distinct. If neither holds, the relative order of equal elements is a function of the algorithm's internals and the input order.

**Failure.** A list is sorted by priority. Items with equal priority come out in different orders on different runs, hosts, or input permutations. If downstream processing is sequential and order-dependent — first-writer-wins, rate allocation, event application — the outcome changes per run.

**Asymmetry.** Each element is in the correct bucket. The sort is correct by its own definition. Only the *interleaving* of equal-key elements is unspecified, and interleaving is not what any dashboard measures.

## What Was Observed

**Signature.** Non-deterministic output from identical input. Tests that pass alone and fail under load. Order-dependent bugs that vanish on re-run and reappear on the next deploy.

**Trace.** A priority queue implemented with a binary heap returns equal-priority items in heap-shape order, which depends on insertion order and the sequence of pops. Two replicas with the same events but different arrival orders produce different visible outcomes for equal-priority events.

**Why monitoring stays green.** Every element is present and correctly grouped. Order-sensitive downstream behavior looks like a logic bug rather than a sort property.

## Condition of Validity

Deterministic ordering holds only while at least one applies:

1. **Stable sort.** The algorithm is documented stable and that stability is preserved across languages and versions.
2. **Total order.** A tiebreaker makes every key distinct, so no equal elements exist to reorder.
3. **Order irrelevance.** Downstream behavior is provably independent of the order of equal-key elements.

Condition 1 is fragile across library upgrades; 2 is the only one that does not depend on implementation.

## Decision Boundary

- Stable sort plus no downstream order dependence: safe, but only as long as the algorithm remains stable.
- Total order via tiebreaker: safe regardless of algorithm.
- Unstable sort with downstream order dependence: non-deterministic by construction.
- Unstable sort plus idempotent downstream: safe if idempotence is verified, unsafe if assumed.

## Operational Effect

The assumption lives in a comment somewhere far from the sort call, and library upgrades routinely change stability guarantees. Remediation is a tiebreaker in the comparator. The trap is to add `sorted(..., reverse=True)` in the belief that direction implies determinism. It does not; direction is orthogonal to stability.

```python
from dataclasses import dataclass


class SortStabilityError(RuntimeError):
    """Raised when downstream assumptions depend on an unstable sort of equal elements."""


@dataclass(frozen=True)
class SortStabilityGate:
    sort_is_stable: bool
    tiebreaker_present: bool
    downstream_order_dependent: bool = True

    def verify(self) -> bool:
        if not self.downstream_order_dependent:
            return True
        if not self.sort_is_stable and not self.tiebreaker_present:
            raise SortStabilityError(
                "unstable sort with order-dependent downstream: equal elements may reorder"
            )
        return True


def dispatch_sort_mode(gate: SortStabilityGate) -> str:
    try:
        gate.verify()
    except SortStabilityError:
        return "add-tiebreaker"
    return "as-configured"
```