Sorting by key: how engineers actually sort

Sorting by key

Real-world sorting is rarely about bare numbers. It is about records: users by signup date, posts by score, files by size.

Python's sorted handles this with the key argument, a function that takes one item and returns the value to sort by. sorted(words, key=len) sorts words by length, because Python calls len on each word and orders by those results.

Three rules make key powerful.

• The key function runs once per item, and the O(n log n) comparisons then happen between the precomputed key values. Even an expensive key stays affordable.
• Keys can be tuples, which compare position by position. key=lambda s: (-s[1], s[0]) means by score with the highest first, since negating a number reverses its order, then by name A to Z among ties.
• reverse=True flips the entire order, which is the tool when negation is awkward, since strings cannot be negated.

There is no separate algorithm to learn here. Every sort in this unit simply routes its comparisons through the key.

Keys and tuple keys

First words by length, then records by score descending with alphabetical tie-breaks.

words = ["pear", "fig", "banana", "kiwi"]
print(sorted(words, key=len))

scores = [("ana", 91), ("bo", 78), ("cy", 91), ("dee", 84)]
print(sorted(scores, key=lambda s: (-s[1], s[0])))

Output

['fig', 'pear', 'kiwi', 'banana']
[('ana', 91), ('cy', 91), ('dee', 84), ('bo', 78)]

key=len passes the function itself rather than calling it, so len runs once per word and the sort compares the resulting numbers.

In the first output, pear came before kiwi even though both have length 4. Nothing in the key distinguishes them, and the next block explains why their input order survived.

The tuple key does two jobs at once. -s[1] sorts scores from high to low, since −91 is less than −78, and s[0] breaks ties alphabetically, which is why ana precedes cy at 91 points.

The order inside the tuple is the priority order. Swapping it to (s[0], -s[1]) would sort by name first and make the score almost irrelevant.

Stability: the invisible guarantee

A sort is stable when items that compare equal keep their original left-to-right order. Python's sort is guaranteed stable, and that guarantee is a tool rather than a detail.

To sort by several criteria you can sort by the secondary key first and then by the primary key, because the second sort preserves the first sort's order among ties. That is often clearer than building one large tuple key.

The reason to care is that users notice. League tables, spreadsheets, and paginated feeds ordered by score with newest first among ties all depend on it.

With an unstable sort, equal-score rows would shuffle on every re-sort, and a list that reorders itself for no visible reason gets filed as a bug.

Look back at the first output in the previous block. pear came before kiwi, both of length 4, precisely because pear came first in the input, and that is stability in action.

Because both have the key −91, and a stable sort keeps equal-key items in their original input order, where ana came first.

The key function returns −91 for both, so as far as the sort is concerned they are indistinguishable. Nothing in the comparison prefers one over the other.

The sorting itself is straightforward: −91 is less than −78, so both 91-scores move to the front. The interesting part is only the order between them.

Python's guarantee resolves it without any tie-break code, since equal-key items keep their input order. ana stays ahead of cy for no reason other than that it was ahead to begin with.

Relying on that is fine when input order is meaningful, such as insertion or timestamp order. When it is not, say the tie-break explicitly with a tuple key like (-s[1], s[0]), because an implicit dependence on input order is fragile.

oldest_first

Names only, oldest first, with age ties broken alphabetically.

def oldest_first(people):
    ranked = sorted(people, key=lambda p: (-p[1], p[0]))
    return [name for name, age in ranked]

print(oldest_first([("maya", 34), ("liam", 41), ("ana", 41), ("kai", 29)]))
print(oldest_first([("bo", 70), ("cy", 70)]))

Output

['ana', 'liam', 'maya', 'kai']
['bo', 'cy']

The tuple key compares position by position, so (-p[1], p[0]) means age descending and then name ascending. The negation handles the descending half, and no reverse=True is needed because that would reverse the names too.

Sorting comes first and the names are stripped afterwards. Mapping to names before sorting would throw away the ages the sort depends on.

The first result shows the tie-break working. ana and liam are both 41, and ana comes first alphabetically, ahead of the younger maya and kai.

The second call is a case where the explicit tie-break and stability agree, since bo precedes cy both alphabetically and in the input. Writing the tie-break anyway is what makes the result independent of how the caller happened to order the data.

Exactly 1,000 times, once per record.

Python computes all 1,000 keys up front, and the O(n log n) comparisons then happen between those precomputed values. The original records are only carried along.

The alternative design would be to call the key inside every comparison, which for 1,000 records at about 10,000 comparisons would mean roughly 10,000 calls instead of 1,000.

That is why even a slow key function is usually affordable. A key that parses a date string costs n parses rather than n log n of them.

It is also why key= beats writing a custom comparison function. A comparator has to run on every comparison by definition, so it cannot benefit from precomputation, and Python dropped direct comparator support for exactly this reason.