Merge sort when stability changes the result
Use stable merge sort to preserve registration order among equal scores, trace the tie decision, and explain what stability does and does not guarantee.

A stable sort preserves the input order of records with equal sorting keys. If a student list is already in registration order, sorting stably by score keeps earlier registrants first within each equal-score group. For a developer displaying rankings or grouped records, that behavior can be visible to users even though both stable and unstable results satisfy the numeric ordering requirement.
Take four records in registration order: Ava with score 91, Ben with 88, Chi with 91, and Dia with 88. Sorting by ascending score should produce Ben, Dia, Ava, Chi if stability is required. The equal-score pairs retain Ben before Dia and Ava before Chi. Sorting alphabetically within each score group would be another valid contract, but stability alone does not add that alphabetical rule.
The merge decides which tied record wins
Merge sort divides the input into halves, sorts each half, and merges the two sorted results. Stability depends on both halves being stable and on the merge choosing a left record first when the keys are equal. Every record in the left half originally appeared before every record in the right half.
def stable_score_sort(records):
if len(records) < 2:
return list(records)
middle = len(records) // 2
left = stable_score_sort(records[:middle])
right = stable_score_sort(records[middle:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i][0] <= right[j][0]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
students = [(91, 'Ava'), (88, 'Ben'), (91, 'Chi'), (88, 'Dia')]
assert stable_score_sort(students) == [
(88, 'Ben'), (88, 'Dia'), (91, 'Ava'), (91, 'Chi'),
]
The comparison looks only at the score in tuple position zero. Comparing complete tuples would use the names to break ties and would implement a different ordering. For example, registration order Zoe then Amy at the same score must remain Zoe then Amy under this contract, even though an alphabetical tuple comparison would reverse them.
At the final merge in the example, the left half is Ben then Ava and the right half is Dia then Chi. Ben and Dia tie, so Ben is emitted first. Dia then beats Ava by score. Ava and Chi tie, so Ava wins that comparison. The final output matches both score order and the original order inside each tie group.
Changing <= to < makes the merge take the right record on equality. That small edit still produces nondecreasing scores, so a test that checks only numeric sortedness would pass. The record identities expose the stability bug.
Prove order and stability separately
The usual merge argument proves sortedness: the next output is the smallest remaining key at the front of either half. It also proves that every input record appears exactly once. Neither statement by itself proves stability.
For two equal-key records originally in the same half, the recursive stability guarantee preserves their order. For equal-key records in different halves, the one from the left originally came first. Choosing the left candidate on every tie preserves that ordering across the halves. These two cases cover every pair of equal-key records, giving an inductive proof of stability.
The base case returns a copy of a zero- or one-record sequence, where there is no pair to reorder. This copying choice means the function does not mutate the caller’s list. The record objects themselves are still shared references; the example does not deep-copy their contents.
Account for the temporary storage
For n records, balanced splitting creates O(log n) recursive levels. At each level, the merge work across the subproblems totals O(n). The resulting runtime is O(n log n), assuming score comparisons and reference moves have constant cost. Princeton’s mergesort chapter develops this divide-and-conquer analysis.
The simple Python implementation creates slices and output lists. Its peak extra storage is O(n), plus O(log n) stack frames; cumulative allocations across the run are larger because temporary lists are created at multiple levels. A production array merge sort commonly reuses a temporary buffer to reduce allocation churn. Neither version is an in-place constant-space sort.
A stable result also needs a consistent key. NaN scores, changing scores during the sort, or a comparator that contradicts itself require an explicit policy. Stability cannot repair a key ordering that has no coherent meaning.
Use stability for multi-key sorting carefully
Suppose the desired final order is score first and registration time second. A single compound key (score, registration_time) states that requirement directly. Another method sorts by registration time first, then performs a stable sort by score. The second pass preserves the ordering established by the first among equal scores. Python’s sorting HOWTO documents this pattern and its stability guarantee.
The order of those passes matters. Sorting by score and then stably by registration time makes registration time the primary key. A stable algorithm preserves earlier decisions only where the later key ties; it does not make the order of sort operations interchangeable.
For testing, attach a registration sequence number to every record and assert that those sequence numbers increase within each equal-score group. Include a tie split across the recursive midpoint, an all-equal group, and names whose alphabetical order opposes registration order. Those inputs distinguish the promised behavior from an accidentally sorted score column.
Trace two stable passes and a tempting reversal
A four-record case makes the multi-key rule observable. Store each record as score, registration sequence, and name. The sequence is an explicit secondary key; it no longer depends on the order in which a database happened to return records. Lower sequence numbers mean earlier registration in this synthetic example.
records = [
(91, 30, 'Ava'), (88, 20, 'Ben'),
(91, 10, 'Chi'), (88, 40, 'Dia'),
]
by_registration = sorted(records, key=lambda row: row[1])
ascending = sorted(by_registration, key=lambda row: row[0])
assert [row[2] for row in by_registration] == ['Chi', 'Ben', 'Ava', 'Dia']
assert [row[2] for row in ascending] == ['Ben', 'Dia', 'Chi', 'Ava']
assert ascending == sorted(records, key=lambda row: (row[0], row[1]))
wrong_pass_order = sorted(
sorted(records, key=lambda row: row[0]), key=lambda row: row[1],
)
assert [row[0] for row in wrong_pass_order] == [91, 88, 91, 88]
highest_first = sorted(by_registration, key=lambda row: row[0], reverse=True)
assert [row[2] for row in highest_first] == ['Chi', 'Ava', 'Ben', 'Dia']
assert [row[2] for row in reversed(ascending)] == ['Ava', 'Chi', 'Dia', 'Ben']
After the registration pass, Chi precedes Ava and Ben precedes Dia. The score pass moves score groups into ascending order while preserving those relationships inside each group. Applying the passes in the opposite order makes registration the final primary key, so the scores can alternate. Stability promises to preserve order only among records tied on the current pass’s key.
Descending score with ascending registration is another distinct contract. Python’s stable reverse=True sort preserves the registration order among equal scores, as the sorting HOWTO’s note about reverse stability states. Reversing the completed ascending list reverses every tie group as well. The two operations agree on the score column but disagree on the record order.
The example uses the standard library to expose pass semantics, not to claim that Python’s built-in sort is this recursive merge implementation. The earlier function always sorts ascending by the first tuple field. If adapting that function for descending scores, choose the left record when scores are equal and reverse only the strict key ordering. Reversing its final output would lose stability just as it does above.
Decide what a tie means across repeated requests
Stable sorting preserves the input order supplied to that invocation. It cannot invent a historical order if two requests receive equal-score rows in different orders. If the application requires reproducible rankings across reloads, include the registration sequence explicitly, and specify what happens when that sequence also ties. A unique record identifier can be a final tie-breaker if that is the product’s intended rule. Adding it changes the ordering contract and should be deliberate.
For an exercise, give two students identical scores and identical registration sequences but different names. A compound key using only score and sequence should preserve their input order; adding the name as a third component may change it. Then check descending score with ascending sequence using the compound key (-score, sequence) for numeric scores. It should match the two-pass result without relying on a reversal of the whole list. These examples separate stability, priority between keys, and an explicit final tie-breaker.