skip to content

Python's sorted() is stable, so why do tied records still swap order between runs of a 340-case regression pack?

level: seniorimportance: should knowfreq 40%

answer

  1. Stable relative to what, exactly?
  2. Where did the input order come from?
  3. One collection type shuffles per process
  4. A diagnostic env var, not a fix
  5. Add a unique tiebreaker to the key

basics

~20 s

Stability preserves the order equal keys arrived in, so it is only as deterministic as the input. A set or a directory listing hands the sort a different order each run. Fix it with a total key that leaves no ties.

solid answer

~50 s

Python guarantees `sorted()` and `list.sort()` are **stable**: elements whose keys compare equal keep their **input** order. That guarantee says nothing about where the input order came from. If a video-metadata extractor sorts the contents of a `set`, string hashing is randomized per process, so set iteration order — and therefore the order of tied records — changes between runs; directory listings, thread or process completion order and merged results from several workers behave the same way. Running the 340-case pack with `PYTHONHASHSEED` fixed is a good **diagnostic** — if the flapping stops, the ordering depends on hash order — but it is a bad fix, because it pins a global to hide a local defect. The real fix is a **total key**: append a unique, stable tiebreaker such as the source path or record id to the tuple key so no two elements ever compare equal.

code

python · 10 lines
python
tags = {"intro", "outro", "teaser", "credits"}

# 'intro' and 'outro' tie on length; their order follows set iteration
flaky = sorted(tags, key=len)

# total key: nothing compares equal, so the result is reproducible
stable = sorted(tags, key=lambda t: (len(t), t))

print(flaky)
print(stable)

go deeper

for a junior

Know the guarantee in plain words: equal elements keep the order they arrived in. That is enough to see why the same sort can produce different output when the input arrives differently.

for a middle

Explain the concrete sources of unordered input — set iteration under per-process string hash randomization, filesystem listings, completion order — and write a tuple key that appends a unique tiebreaker.

for a senior

Show the full diagnosis: reproduce with a pinned hash seed to confirm hash-order dependence, then reject that as the fix and make the key total. Know that reverse=True never reorders ties.

for a principal

Own the contract question — decide whether intra-tie order is part of your output's public contract at all, and set the standard that any serialized, diffed or hashed ordering must be total by construction.

## What the stability guarantee actually promises Python documents that its sorts are stable: *elements that compare equal retain their original relative order*. "Original" means **the order in which the sort received them**. Stability is a property that transports input order into output order; it does not create an order out of nothing. So the determinism of a sorted result is the conjunction of two things: a deterministic input sequence, and a key that distinguishes the elements you care about distinguishing. A regression pack that asserts on exact output ordering is quietly depending on both. ## Where non-deterministic input order comes from A video-metadata extractor that collects work items into a `set` for de-duplication and then sorts them by duration is the archetype. Since Python 3.3, the hashes of `str` and `bytes` are randomized per process, so the iteration order of a set of strings differs between runs. Sorting stabilises the primary key — duration — but every group of equal durations comes out in whatever order that process's set iteration happened to produce. Across 340 cases, a handful contain ties, and those are the ones that flap. The same shape appears elsewhere: - **Filesystem listings.** `os.listdir` and `os.scandir` return entries in filesystem order, which is not sorted and not guaranteed stable across machines or after file churn. - **Concurrent completion order.** Results collected as workers finish arrive in a timing-dependent order; a slow worker under load reorders the batch, which is why the same pack can also show up as an intermittent timeout on one run and a diff on the next. - **Merged sources.** Chunks combined from several producers arrive interleaved differently each time. - **Sets of any hashable objects**, not only strings, when the objects' hashes derive from strings. A `dict` is *not* on this list: insertion order has been part of the language since 3.7, so a dict built by a deterministic sequence of inserts iterates deterministically. ## Confirming the diagnosis before changing code Re-run the failing cases with `PYTHONHASHSEED` set to a fixed value. If the ordering becomes reproducible, the pipeline depends on hash order somewhere upstream. That is a **diagnostic**, not a remedy: pinning the variable turns a global environment setting into load-bearing test infrastructure, hides the same defect in production where nothing pins it, and gives up the hash-collision protection randomization exists for. Similarly, sorting a set into a list first changes nothing — the list simply freezes whichever arbitrary order that run produced. ## The fix: make the key total A sort order is deterministic when no two distinct elements produce equal keys. Extend the tuple key with a field that is unique and stable across runs — a source path, a record id, a content digest, an ingestion sequence number: ```python items.sort(key=lambda m: (m.duration, m.source_path)) ``` Now ties in `duration` are broken by something that does not depend on how the items reached the sort. The regression pack asserts a genuine ordering rather than an accident, and the same code produces the same output on another machine, in another process, and after the collection upstream is refactored. When no natural tiebreaker exists, the alternative is to stop asserting on a total order: compare the output as a multiset, or group by the primary key and compare groups. That is honest — it says "the order within a tie is not part of the contract" — where a pinned hash seed says "it is, and I have frozen the universe to make it true". ## Two related traps **`reverse=True` does not reverse ties.** The sort stays stable under `reverse=True`; equal elements keep their input order rather than appearing flipped. So toggling `reverse` will never repair tie non-determinism, and a two-pass sort that assumes ties get mirrored is wrong. **Key cost is per element, not per comparison.** If the tiebreaking field is expensive — probing each file for a duration, say — remember the key runs exactly once per element, so `n` probes, not `n log n`. If `n` probes is still the source of an intermittent timeout on a large case, precompute the field once when the record is created and sort on the stored value, rather than doing I/O inside the key at all. ## The reviewable rule Any sort whose output is asserted, serialized, hashed or diffed should have a key that is total by construction. Treat "the sort is stable so the order is fixed" as an incomplete argument: stability is only half of it, and the other half is whoever built the input.

  • Why is fixing PYTHONHASHSEED in the test runner a poor permanent fix?
    It makes a global interpreter setting load-bearing for correctness, so the defect survives anywhere the variable is not set — production, another CI image, a developer shell. It also disables the protection randomization exists for, and it hides rather than removes the dependency on an arbitrary order. Use it once to confirm the diagnosis, then make the sort key total so the ordering is correct regardless of hashing.
  • The key that breaks ties probes each file for its duration and the pack sometimes times out. Does that cost scale with comparisons?
    No — the key runs exactly once per element, so it is n probes, not n log n. If n probes still blows the budget, the problem is doing I/O inside the sort at all: capture the duration when the record is first built, store it on the record, and sort on the stored field. That also removes a source of run-to-run variation, since a probe that intermittently times out can otherwise change the key itself.
  • If the elements have no natural unique tiebreaker, what should the regression assertions do instead?
    Stop asserting a total order. Compare the results as a multiset, or group by the primary key and assert the groups' contents, which states honestly that intra-tie order is not part of the contract. An alternative is to add a deterministic ingestion sequence number at the point items are created, which manufactures the missing tiebreaker rather than pretending the order is meaningful.

A stable sort is a careful librarian who never reshuffles two books with the same title — but if the cart arrives in a different order each morning, the shelf still looks different each day.

saying these in an interview costs you the question

  • Thinks stability guarantees one fixed output regardless of input
  • Fixes the flake by pinning PYTHONHASHSEED in CI
  • Blames the sort algorithm for being unstable
  • Says converting the set to a list makes the order deterministic
  • Expects reverse=True to change how ties are ordered
  • Assumes dict iteration is as unordered as set iteration

context

resolving links…