Sorting and key functions

Sorting numbers is easy. Real data comes as records: players with scores, files with sizes, orders with dates. Python’s sorting tools handle these with one idea, the key function, which you met briefly in lambdas and higher-order functions. How sorting works in general, and what it costs, is covered in searching and sorting in the fundamentals track. This lesson is about using Python’s sort well: the helpers, the guarantee of stability, and how to combine keys.

sorted, sort and key

sorted(iterable) returns a new list and leaves the input alone. list.sort() sorts a list in place and returns None. Both accept key, a function called once per item, and reverse:

words = ["banana", "Apple", "cherry", "apple", "Banana"]

print(sorted(words))
print(sorted(words, key=str.casefold))
print(sorted(words, key=len))
print(sorted(words, key=len, reverse=True))
print(words)

['Apple', 'Banana', 'apple', 'banana', 'cherry']
['Apple', 'apple', 'banana', 'Banana', 'cherry']
['Apple', 'apple', 'banana', 'cherry', 'Banana']
['banana', 'cherry', 'Banana', 'Apple', 'apple']
['banana', 'Apple', 'cherry', 'apple', 'Banana']

The default order puts every capital letter before every lower-case one. key=str.casefold compares a folded version of each word, which is what people expect for names. The key is only used for comparing: the items in the result are the original words. The last line shows that words is untouched.

The in-place version changes the list and returns None, a classic stumbling block:

copy = words.copy()
result = copy.sort(key=str.casefold)
print(result, copy)

None ['Apple', 'apple', 'banana', 'Banana', 'cherry']

Writing words = words.sort() leaves you with None. Use sorted unless you specifically want in-place work on a large list.

itemgetter and attrgetter

Sorting rows or dictionaries by one field is so common that operator has ready-made key functions. itemgetter(i) picks item[i], and works for tuples, lists and dictionary keys. attrgetter("name") picks obj.name. They are quicker than the equivalent lambda and read more clearly:

from dataclasses import dataclass
from operator import attrgetter, itemgetter

rows = [("ada", 31), ("grace", 28), ("alan", 41)]
print(sorted(rows, key=itemgetter(1)))

records = [{"name": "ada", "score": 90}, {"name": "alan", "score": 75}]
print(sorted(records, key=itemgetter("score")))
print(itemgetter("name", "score")(records[0]))

[('grace', 28), ('ada', 31), ('alan', 41)]
[{'name': 'alan', 'score': 75}, {'name': 'ada', 'score': 90}]
('ada', 90)

Given several arguments, itemgetter returns a tuple, which is also a valid key for sorting by several fields. For objects, use attrgetter:

@dataclass
class Player:
    name: str
    points: int


players = [Player("ada", 5), Player("alan", 9)]
print([p.name for p in sorted(players, key=attrgetter("points"), reverse=True)])

['alan', 'ada']

Stability

Python’s sort is stable: items that compare equal keep their original relative order. That is a guarantee in the language documentation, and it is what makes multi-step sorting reliable:

from operator import itemgetter

people = [("grace", "B"), ("alan", "A"), ("ada", "B"), ("barbara", "A")]

by_group = sorted(people, key=itemgetter(1))
print(by_group)

[('alan', 'A'), ('barbara', 'A'), ('grace', 'B'), ('ada', 'B')]

Within each group, the people are in the order they had in the input: grace before ada, because that is how they came. Nothing was shuffled. reverse=True also preserves the original order of equal items; it does not simply reverse the final list.

Stability gives you a recipe: to sort by group and then, within each group, by name, sort by the less important key first, then by the more important one:

step1 = sorted(people, key=itemgetter(0))
step2 = sorted(step1, key=itemgetter(1))
print(step2)

[('alan', 'A'), ('barbara', 'A'), ('ada', 'B'), ('grace', 'B')]

The second sort moved people between groups but, being stable, never reordered those within a group, so the names from the first sort survived.

Mixed directions

Sorting by several fields with a tuple key works when all fields go the same way. For mixed directions, you have two options. For numbers, negate the value so that bigger sorts first. For anything, you can sort twice and rely on stability:

from operator import itemgetter

scores = [("ada", 90), ("alan", 90), ("grace", 75), ("barbara", 90)]

# Highest score first, then name A to Z. Negate the number...
print(sorted(scores, key=lambda row: (-row[1], row[0])))

# ...or sort twice, least important key first.
step1 = sorted(scores, key=itemgetter(0))
step2 = sorted(step1, key=itemgetter(1), reverse=True)
print(step2)

[('ada', 90), ('alan', 90), ('barbara', 90), ('grace', 75)]
[('ada', 90), ('alan', 90), ('barbara', 90), ('grace', 75)]

Both give the same result. Negating cannot work on text, so when you need, say, score ascending and name descending, use two passes:

by_name_desc = sorted(scores, key=itemgetter(0), reverse=True)
print(sorted(by_name_desc, key=itemgetter(1)))

[('grace', 75), ('barbara', 90), ('alan', 90), ('ada', 90)]

Common pitfalls

• Assigning the result of .sort(). It returns None.
• Comparing mixed types. Sorting [3, "a"] raises TypeError: '<' not supported between instances of 'str' and 'int'. Make the key return one comparable type.
• Expecting case-insensitive order by default. Use key=str.casefold.
• Sorting in the wrong order of passes. With two passes, the last sort is the most important key.
• Negating a non-numeric key. -"abc" is a TypeError. Use the two-pass method.

1. Ben    150  70.0
2. Omar   150  70.0
3. Lena   120  58.2
4. Mei    120  61.5
5. Ana     90  40.0

entries = [
    {"name": "Mei", "points": 120, "time": 61.5},
    {"name": "Omar", "points": 150, "time": 70.0},
    {"name": "Lena", "points": 120, "time": 58.2},
    {"name": "Ben", "points": 150, "time": 70.0},
    {"name": "Ana", "points": 90, "time": 40.0},
]

entries = [
    {"name": "Mei", "points": 120, "time": 61.5},
    {"name": "Omar", "points": 150, "time": 70.0},
    {"name": "Lena", "points": 120, "time": 58.2},
    {"name": "Ben", "points": 150, "time": 70.0},
    {"name": "Ana", "points": 90, "time": 40.0},
]

ranking = sorted(entries, key=lambda e: (-e["points"], e["time"], e["name"]))
for place, entry in enumerate(ranking, start=1):
    print(f"{place}. {entry['name']:<5} {entry['points']:>4} {entry['time']:>5.1f}")

1. Ben    150  70.0
2. Omar   150  70.0
3. Lena   120  58.2
4. Mei    120  61.5
5. Ana     90  40.0

pairs = [("b", 1), ("a", 1), ("c", 0)]
print(sorted(pairs, key=lambda p: p[1]))

[('c', 0), ('b', 1), ('a', 1)]

[('A', 'carl'), ('A', 'adam'), ('B', 'Zoe'), ('B', 'Bea')]

students = [
    {"name": "Zoe", "grade": "B"},
    {"name": "adam", "grade": "A"},
    {"name": "Bea", "grade": "B"},
    {"name": "carl", "grade": "A"},
]

from operator import itemgetter

students = [
    {"name": "Zoe", "grade": "B"},
    {"name": "adam", "grade": "A"},
    {"name": "Bea", "grade": "B"},
    {"name": "carl", "grade": "A"},
]

# Grade A to Z, then name Z to A ignoring case: two stable passes.
step1 = sorted(students, key=lambda s: s["name"].casefold(), reverse=True)
step2 = sorted(step1, key=itemgetter("grade"))
print([(s["grade"], s["name"]) for s in step2])

[('A', 'carl'), ('A', 'adam'), ('B', 'Zoe'), ('B', 'Bea')]

Summary

• sorted() returns a new list, and .sort() changes the list in place and returns None. Both take key and reverse.
• itemgetter and attrgetter are neat key functions for records and objects. A tuple key sorts by several fields.
• Sorting is stable, so for mixed directions you can sort in several passes, least important key first.
• This ends the module. Next up: testing and debugging.