Relying on Sort Stability

Concepts covered: Dictionaries, Lambda, Sorting, Tuples

A sort is stable when rows with equal keys come out in the same relative order they went in. The Python documentation guarantees stability for both sorted() and list.sort(), and states that reverse=True keeps the guarantee. Interviewers ask about it because 2 everyday techniques depend on it: chaining sorts, and deduplicating by keeping one record per key.

rows = [('Nova', 30), ('Kite', 50), ('Arlo', 30), ('Mira', 50)]
print(sorted(rows, key=lambda r: r[1]))
print(sorted(rows, key=lambda r: r[1], reverse=True))

The first line prints [('Nova', 30), ('Arlo', 30), ('Kite', 50), ('Mira', 50)] and the second prints [('Kite', 50), ('Mira', 50), ('Nova', 30), ('Arlo', 30)]. In both, Nova stays ahead of Arlo and Kite stays ahead of Mira, matching their positions in rows. reverse=True inverts the comparison while holding equal rows in their original sequence; reversing the finished ascending list would have put Mira before Kite.

Chaining sorts, least important field first

Stability turns a multi-field sort into a sequence of single-field sorts. Sort by the least important field first and by the most important field last. Each later pass reorders only by its own field, and among rows that tie on it, the order left by the earlier pass survives. This solves the case a tuple key cannot express: 2 string fields in opposite directions, such as artist from Z to A with tracks from A to Z inside each artist.

plays = [
    ('Nova', 'Halo'),
    ('Kite', 'Pulse'),
    ('Nova', 'Aster'),
    ('Kite', 'Drift'),
    ('Arlo', 'Ember'),
]
plays.sort(key=lambda r: r[1])
print(plays)
plays.sort(key=lambda r: r[0], reverse=True)
for artist, track in plays:
    print(artist, track)

[('Nova', 'Aster'), ('Kite', 'Drift'), ('Arlo', 'Ember'), ('Nova', 'Halo'), ('Kite', 'Pulse')]
Nova Aster
Nova Halo
Kite Drift
Kite Pulse
Arlo Ember

After the first pass the tracks run Aster, Drift, Ember, Halo, Pulse. The second pass groups by artist from Z to A, and within Nova and within Kite the tracks keep the alphabetical sequence the first pass produced. Neither field is a number, so no negation trick could have produced this order in one call.

Chained stable passes

• Handles any field type in either direction
• Costs one full sort per field
• Pass order runs opposite to the spec, a common slip

One tuple key

• One sort and one key call per row
• A descending slot needs a negatable value
• Reads as a single ordering rule in review

Deduplicating: keep the latest record per key

A classic pipeline task: a change feed delivers several versions of each customer row, and the target table needs only the newest version per customer_id. Sort the events by updated_at ascending, then write them into a dict keyed by customer_id. Later writes overwrite earlier ones, so each key ends holding its newest version. Stability settles the hard case. When 2 versions share an updated_at, they stay in arrival order, so the one that arrived last wins, a rule you can state and defend.

events = [
    {'customer_id': 7, 'updated_at': '2024-03-02T10:00', 'tier': 'silver'},
    {'customer_id': 9, 'updated_at': '2024-03-01T08:00', 'tier': 'free'},
    {'customer_id': 7, 'updated_at': '2024-03-01T09:00', 'tier': 'free'},
    {'customer_id': 7, 'updated_at': '2024-03-02T10:00', 'tier': 'gold'},
    {'customer_id': 9, 'updated_at': '2024-03-03T12:00', 'tier': 'plus'},
]

latest = {}
for e in sorted(events, key=lambda e: e['updated_at']):
    latest[e['customer_id']] = e

for cid in sorted(latest):
    print(cid, latest[cid]['tier'])

The program prints 7 gold and 9 plus. ISO 8601 strings in a single fixed format and timezone order the same way as the instants they encode, so no parsing is needed. Customer 7 has 2 versions at 2024-03-02T10:00; the sort keeps silver ahead of gold, and the dict keeps gold. With an unstable sort, which of silver and gold survives would depend on the algorithm's internals rather than on arrival order, so the result could change when the feed's order or the library changes.

The keep-first variant

To keep the earliest version per key instead, sort the same way and skip any key already present: if e['customer_id'] not in first: first[e['customer_id']] = e. Stability again decides ties, this time in favour of the version that arrived first.

About this lesson

This section is part of the Custom Sorting: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.