Experiments and implementations · Intermediate

Testing sorting stability with records

Label equal-key records and test what stable sorting preserves, including a two-key multi-pass example.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Equal keys do not make records interchangeable
  2. Run with an explicit key function
  3. Compose stable passes in the right order
  4. Stability preserves the order actually supplied
  5. Specify collation and missing-value behavior separately
  6. Test order before measuring speed
  7. Ask Logeia about this articleCheck your understanding

Equal keys do not make records interchangeable

A stable sort preserves the input order of records that compare equal under the selected key. Use A and C with key two, and B and D with key one, presented as A2, B1, C2, D1. Printing only one, one, two, two cannot reveal stability, because the identity of each record has disappeared. Keep the labels and verify B before D and A before C. This property does not mean every record keeps its original absolute position. It means that relative order within each equal-key group survives the reordering into key order.

Run with an explicit key function

Pass a key function selecting the integer to Python sorted. Sorting the complete tuple instead introduces the label as another comparison component and changes which records count as equivalent. Also distinguish sorted, which creates a new list, from list.sort, which rearranges the existing list. The assertions check the output labels and preservation of the input list. Choose the API according to whether callers need the original order later. A correct sorting algorithm can still be used incorrectly if subsequent code assumes an input was mutated when it was copied, or assumes a copy when a shared list was modified.

Python 3
records = [("A", 2), ("B", 1), ("C", 2), ("D", 1)]
ordered = sorted(records, key=lambda row: row[1])
assert [r[0] for r in ordered] == ["B", "D", "A", "C"]
assert records == [("A", 2), ("B", 1), ("C", 2), ("D", 1)]
# A multi-pass stable sort: secondary key first, primary key last.
rows = [("x", 2), ("y", 1), ("x", 1), ("y", 2)]
by_secondary = sorted(rows, key=lambda row: row[1])
by_both = sorted(by_secondary, key=lambda row: row[0])
assert by_both == sorted(rows, key=lambda row: (row[0], row[1]))
print(ordered, by_both)

Compose stable passes in the right order

For records with a string primary key and integer secondary key, sort by the secondary key first and the primary key last. The final stable pass preserves the established secondary order within each primary group. Compare that result with one sort using the pair of keys. Reversing the passes generally gives the secondary key final precedence and therefore a different contract. This experiment makes a useful composition rule visible: less significant ordering is established first when later stable passes must retain it inside groups. It is not a reason to perform unnecessary multiple passes when one clear composite key already expresses the desired policy.

Stability preserves the order actually supplied

A stable sort preserves the input order it receives. If external retrieval or parallel collection supplies a different order each time, stability does not eliminate that variability. Reproducible presentation may require an explicit tie-breaking key such as a timestamp and unique identifier. Adding such a key is a policy decision distinct from preserving an existing order among equivalent records. Decide whether the application wants reproducibility, respect for a prior ranking, or both. Otherwise, a developer may incorrectly attribute changes to an unstable algorithm even though the sorting contract is satisfied and the source order itself changed.

Specify collation and missing-value behavior separately

The example uses simple integers and labels. Case folding, language-specific collation and placement of missing values are separate requirements. A case-folding key can make differently displayed strings compare equal; stability then applies to those transformed keys. Do not mix incomparable types or use ordering state that changes during the operation without defining a valid contract. Tests should state what the comparison means, not merely check that an output looks approximately alphabetical. Stability cannot repair an unsuitable key function, and it does not turn a code-point comparison into a locale-aware human dictionary order.

Test order before measuring speed

First assert both nondecreasing keys and the order within equal-key groups. Only then measure performance if it is relevant. Four records do not predict large-workload latency; existing runs, key computation and representation all affect the cost. Stability also does not imply zero auxiliary storage. When moving the experiment to another language or library, check its documented stability contract and rerun the same labeled example. An observed order in one execution is weaker evidence than an API guarantee. Keep correctness checks, resource measurements and claims about implementation strategy separate so each conclusion is supported by the appropriate observation.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path