Python’s sorted() and list.sort() are guaranteed to be stable. If two items compare equal under the sort key, they come out in the same order they went in. That guarantee sounds like a footnote, but it’s what makes multi-field sorting simple, and it explains a few behaviours that surprise people, like why reverse=True and reversing the output aren’t the same thing. This guide works through a small set of orders so you can check each claim against real output (Python 3.14).
from operator import itemgetter
orders = [
{"id": 1, "customer": "ben", "total": 40, "placed": "09:05"},
{"id": 2, "customer": "ana", "total": 75, "placed": "09:10"},
{"id": 3, "customer": "ben", "total": 75, "placed": "09:12"},
{"id": 4, "customer": "ana", "total": 40, "placed": "09:20"},
]What stability actually promises
Sort by total and look at the ids:
print([o["id"] for o in sorted(orders, key=itemgetter("total"))])[1, 4, 2, 3]Orders 1 and 4 both total 40. They come out as 1 then 4, the order they had in the input. Same for 2 and 3 at 75. An unstable sort (C’s qsort, for example, makes no promise) could legally return [4, 1, 3, 2]. With Python, you’ll never see that.
The algorithm behind this is Timsort, a merge sort and insertion sort hybrid designed for real-world data, which often contains already-sorted runs. (Python 3.11 switched its merge strategy to “powersort,” a refinement of how runs are combined; the stability guarantee didn’t change.) In an interview you don’t need the internals. You need to know: O(n log n) worst case, close to O(n) on nearly sorted input, stable, and it sorts in place for list.sort() while sorted() returns a new list.
Sorting by several fields
There are two ways to sort by customer, then by total within each customer.
A tuple key. Tuples compare element by element, so the first field decides, and the second only breaks ties:
print([o["id"] for o in sorted(orders, key=itemgetter("customer", "total"))])[4, 2, 1, 3]ana (40, then 75), then ben (40, then 75). itemgetter with several names returns a tuple, which is a little faster than an equivalent lambda.
Several passes, least significant first. Stability lets you sort by the secondary field, then by the primary one. The second sort keeps the first sort’s order among equal primary keys. This is how you’d sort by customer ascending and, within each customer, newest order first:
s = sorted(orders, key=itemgetter("placed"), reverse=True)
s.sort(key=itemgetter("customer"))
print([(o["customer"], o["placed"]) for o in s])[('ana', '09:20'), ('ana', '09:10'), ('ben', '09:12'), ('ben', '09:05')]The order of the passes is what people get backwards. The last sort is the most significant, because it’s the one that does the final arrangement. If you sorted by customer first and then by time, customers would end up mixed together.
The multi-pass approach shines when fields need opposite directions and one of them can’t be negated. For numbers, a tuple with a negated value also works:
print([o["id"] for o in sorted(orders, key=lambda o: (o["customer"], -o["total"]))])[2, 4, 3, 1]Customer ascending, total descending. You can’t negate a string or a timestamp string, though, which is where two stable passes are the clean solution.
reverse=True is not the same as reversing
This one makes a good quick interview question:
print([o["id"] for o in sorted(orders, key=itemgetter("total"), reverse=True)])
print([o["id"] for o in sorted(orders, key=itemgetter("total"))[::-1]])[2, 3, 1, 4]
[3, 2, 4, 1]Both put the 75s before the 40s. But reverse=True preserves stability: ties stay in input order (2 before 3, 1 before 4). Reversing the sorted list afterwards reverses everything, including the order of ties. If the input was already ordered by something meaningful, like arrival time, [::-1] silently scrambles it. Use reverse=True.
Key functions: called once, and must be comparable
The key function is called exactly once per item, and the results are cached for the duration of the sort. Counting calls while sorting 1,000 numbers:
key calls: 1000That’s why an expensive key (parsing a date, normalising a string) is fine: it costs n calls, not n log n. Older Python had a cmp= parameter that compared pairs; it was removed in Python 3. If you have a comparison function, functools.cmp_to_key adapts it, but a proper key is usually simpler. Version strings are the classic case:
vs = ["1.10.0", "1.2.0", "1.9.3"]
print(sorted(vs))
print(sorted(vs, key=lambda v: tuple(map(int, v.split(".")))))['1.10.0', '1.2.0', '1.9.3']
['1.2.0', '1.9.3', '1.10.0']Plain string sorting puts 1.10.0 first because "1" sorts before "2" character by character. Converting to a tuple of ints gives the numeric order. (For real version strings with suffixes like rc1, use packaging.version.Version as the key.)
Every key must be comparable with every other. Python 3 won’t compare None with an int:
rows = [{"score": 3}, {"score": None}, {"score": 1}]
sorted(rows, key=itemgetter("score"))TypeError: '<' not supported between instances of 'NoneType' and 'int'Decide where missing values go and encode that in the key. A tuple whose first element is a boolean does it neatly:
print(sorted(rows, key=lambda r: (r["score"] is None, r["score"] or 0)))[{'score': 1}, {'score': 3}, {'score': None}]False sorts before True, so real scores come first and None goes last. The or 0 only exists so the second element is always an int.
Text is harder than it looks
Default string sorting compares Unicode code points, so all uppercase letters come before lowercase ones:
names = ["bob", "Alice", "carol", "Émile", "Straße", "STRASSE"]
print(sorted(names))
print(sorted(names, key=str.casefold))['Alice', 'STRASSE', 'Straße', 'bob', 'carol', 'Émile']
['Alice', 'bob', 'carol', 'Straße', 'STRASSE', 'Émile']casefold is the right choice over lower for case-insensitive comparison: it maps ß to ss, so Straße and STRASSE get equal keys and stability keeps them in input order. É still lands after c, though, because its code point is higher than any ASCII letter. Sorting text the way a French or German reader expects requires locale-aware collation (locale.strxfrm or the PyICU library), which is worth mentioning if the interview is about a user-facing feature.
Interview practice: a leaderboard
You have player records with name, score and finished_at (a datetime). The leaderboard should show the highest score first; among equal scores, whoever finished earlier ranks higher; and if both match, sort by name alphabetically. Write the sort and explain your choice.
Answer
A single tuple key does it: sorted(players, key=lambda p: (-p["score"], p["finished_at"], p["name"])). Score is negated to get descending order while the other two fields stay ascending, and tuple comparison applies them in priority order. Negation works because scores are numbers. If the descending field were a string or datetime, I’d use stable passes instead, least significant first: players.sort(key=itemgetter("name")), then players.sort(key=itemgetter("finished_at")), then players.sort(key=itemgetter("score"), reverse=True). Stability guarantees each pass keeps the previous ordering among ties, and reverse=True on the last pass doesn’t disturb ties. I’d also ask whether score can be missing. If so, the key needs an explicit rule, such as (p["score"] is None, -(p["score"] or 0), ...), otherwise the sort raises TypeError the first time a None meets an int.