The pattern that lets you sort by something the items do not contain — and call the key once while doing it.
items = ['bb', 'a', 'ccc']
# Build pairs of (key, item), sort the pairs, throw the keys away
decorated = [(len(item), item) for item in items] # key: once each
decorated.sort(key=lambda pair: pair[0])
[item for _, item in decorated] # -> ['a', 'bb', 'ccc']
# Why key=lambda pair: pair[0] and not just sort()
[(1, {'a': 1}), (1, {'b': 2})] # sorting these compares the dicts
sorted([1, None]) # TypeError: '<' not supported
- The decoration is how you keep the key to one call
Computing key(item) once, into a pair, means the sort compares numbers it already has rather than re-deriving them. sorted(key=...) does exactly this internally — the pattern is only worth writing out by hand when you need to do something to the keys before sorting, which is precisely the None problem.
- Sort on the key alone, not on the pair
Sorting pairs compares the second element whenever the first ties, so two items with the same key get compared directly — and if they are dictionaries or objects with no ordering, that raises. Keying the sort on pair[0] means ties are left to the sort’s stability, which is what you wanted anyway.
- None has no order, so it cannot be sorted — only placed
Python refuses to compare None with anything, which is a feature: there is no correct answer to whether None is less than 5. So the missing keys have to be separated out and put somewhere by decision. Last, in both directions, is the useful default — the holes stay out of the way whichever end you are reading from.
Compute every key first, into pairs. Then you can look at which ones are None and deal with those separately from the ones you can actually sort.
decorated = [(key(item), item) for item in items] calls the key once each. Split that into the pairs whose key is None and the rest, sort the rest, then join: sorted items first, missing ones after.
Sort with key=lambda pair: pair[0] rather than sorting the pairs themselves — otherwise a tie compares the items, and dictionaries raise when compared. The missing ones are appended after the reverse has been applied, so reverse never moves them.
def sort_by(items, key, reverse=False): decorated = [(____(item), item) for item in items] present = [pair for pair in decorated if pair[0] is not ____] missing = [pair for pair in decorated if pair[0] ____ None] present.sort(key=lambda pair: pair[____], reverse=reverse) return [item for _, item in present + ____]
def sort_by(items, key, reverse=False):
# One call per item, and the keys are kept so the sort never
# recomputes them.
decorated = [(key(item), item) for item in items]
present = [pair for pair in decorated if pair[0] is not None]
missing = [pair for pair in decorated if pair[0] is None]
# Keyed on the first element only: a tie must not fall through to
# comparing the items, which may not be comparable at all.
present.sort(key=lambda pair: pair[0], reverse=reverse)
return [item for _, item in present + missing]
Because they are concatenated once the sorting is finished, reverse cannot touch them — they are last whichever direction the rest is running in. The tempting alternative, key=lambda item: (key(item) is None, key(item)), puts them last only when ascending, and calls the key twice per comparison batch into the bargain.
A key of 0, '' or False is a real value that sorts perfectly well, and a truthiness test would banish all of them to the end alongside the genuine holes. Missing means missing; falsy means small.
Splitting after decorating is what keeps the key to one call — filtering the original items would need key(item) again in each condition. It is the same reasoning as partition-by: work out the answer once and then route on it.
If none of the keys can be None, use sorted() directly — this exists for the holes. If you want the missing ones first instead, that is a different function or a flag, and it is worth being explicit rather than clever. For records from a database, the sort belongs in the query, where NULLS LAST is a phrase SQL already understands and an index can serve it. And if the key is expensive rather than merely present-or-not, the decoration here is exactly what functools.cache on the key function would give you for free.
- Add a missing_first flag and check that reverse and it are genuinely independent.
- Let the caller pass a default to use in place of None, and decide whether that is simpler than the two-list split.
- Sort by several keys with different directions by reusing sort-records, and work out where the None handling would have to go.