Sorting with sorted and key functions

Why this matters

Sorting is everywhere: the newest files first, the biggest expenses, a leaderboard, names in alphabetical order regardless of case. Python makes sorting a one-liner, but the one-liner hides decisions you have to get right: do you want a new list or to reorder the existing one, by what criterion, in which direction, and what happens to ties? This lesson answers all of these and introduces lambda, the small anonymous function you will use for key functions everywhere.

Two ways to sort

nums = [5, 2, 9, 1]

new = sorted(nums)     # returns a new list
print(new, nums)       # [1, 2, 5, 9] [5, 2, 9, 1]

nums.sort()            # sorts this list in place, returns None
print(nums)            # [1, 2, 5, 9]

sorted always returns a list, whatever it was given: sorted("cab") is ['a', 'b', 'c'], and sorted({"b": 1, "a": 2}) sorts the dict's keys. Use list.sort() when you own the list and do not need the old order; it avoids making a copy.

How elements are compared

Sorting uses < between elements. Numbers compare numerically. Strings compare lexicographically: character by character, by Unicode code point, like a dictionary that puts all uppercase letters before lowercase:

>>> sorted(["banana", "Cherry", "apple"])
['Cherry', 'apple', 'banana']
>>> "Z" < "a"
True
>>> sorted(["10", "9", "100"])
['10', '100', '9']

The last one surprises people: as text, "10" comes before "9" because "1" < "9". Convert to numbers if you want numeric order.

Tuples and lists compare element by element: the first elements decide, and only if they are equal do the second elements matter, and so on:

>>> sorted([(2, "b"), (1, "z"), (2, "a")])
[(1, 'z'), (2, 'a'), (2, 'b')]

Mixed types that cannot be ordered raise an error:

>>> sorted([3, "two", 1])
TypeError: '<' not supported between instances of 'str' and 'int'

reverse=True

Both sorted and sort take reverse=True for descending order:

>>> sorted([5, 2, 9, 1], reverse=True)
[9, 5, 2, 1]

key functions

Often you do not want to compare the elements themselves but something derived from them: their length, a lowercased version, one field of a record. The key= argument takes a function that is called once per element; the sort then orders the elements by those computed keys.

>>> words = ["kiwi", "fig", "banana", "apple"]
>>> sorted(words, key=len)
['fig', 'kiwi', 'apple', 'banana']
>>> sorted(["banana", "Cherry", "apple"], key=str.lower)
['apple', 'banana', 'Cherry']

Note that you pass the function itself, len, not the result of calling it, len(). Functions are objects; you can hand them to other functions like any value. Underneath, Python computes all the keys first (one call per element), then sorts the elements using the keys, so the key function never sees comparisons and is never called more than once per item:

elements:  "kiwi"  "fig"  "banana"  "apple"
keys:        4       3       6        5
sorted by key:  "fig"(3) "kiwi"(4) "apple"(5) "banana"(6)

The result still contains the original elements, not the keys.

lambda: a function in an expression

For one-off keys you often need a tiny function that is not built in, such as "the second element of a tuple". You could define one with def:

def points(record):
    return record[1]

results = [("ann", 7), ("bo", 3), ("cy", 5)]
print(sorted(results, key=points))   # [('bo', 3), ('cy', 5), ('ann', 7)]

A lambda expresses the same function inline:

sorted(results, key=lambda record: record[1])

lambda params: expression creates a function object with no name whose body is a single expression, implicitly returned. lambda record: record[1] is exactly equivalent to the points function above. Lambdas cannot contain statements (no if blocks, loops or assignments), which keeps them short. If a key needs more than one simple expression, write a named function with def and a docstring instead.

More examples:

people = [{"name": "ann", "age": 31}, {"name": "bo", "age": 25}]
sorted(people, key=lambda p: p["age"])          # youngest first

prices = {"tea": 3.5, "coffee": 2.8, "juice": 4.1}
sorted(prices, key=lambda item: prices[item])   # ['coffee', 'tea', 'juice']
sorted(prices.items(), key=lambda kv: kv[1])    # [('coffee', 2.8), ('tea', 3.5), ('juice', 4.1)]

Stability and ties

Python's sort (an algorithm called Timsort, designed for Python in 2002; since 3.11 it uses an improved rule, from the Powersort algorithm, for deciding which runs to merge) is stable: elements whose keys are equal keep their original relative order.

>>> sorted(["bb", "a", "cc", "d"], key=len)
['a', 'd', 'bb', 'cc']

"a" came before "d" in the input, so it stays first; same for "bb" and "cc". Stability holds with reverse=True too: reversing does not flip the order of ties.

Stability makes multi-pass sorting possible: sort by the least important key first, then by the more important one. The second sort keeps the first sort's order among ties.

records = [("ann", "Oslo"), ("bo", "Bergen"), ("cy", "Oslo"), ("al", "Bergen")]
step1 = sorted(records, key=lambda r: r[0])           # by name
step2 = sorted(step1, key=lambda r: r[1])             # by city; names stay sorted within a city
print(step2)

[('al', 'Bergen'), ('bo', 'Bergen'), ('ann', 'Oslo'), ('cy', 'Oslo')]

Multi-key sorts with tuple keys

Because tuples compare element by element, a key that returns a tuple sorts by several criteria in one pass:

students = [("cy", 85), ("ann", 92), ("bo", 85)]
sorted(students, key=lambda s: (s[1], s[0]))
# [('bo', 85), ('cy', 85), ('ann', 92)]   by score, then name

To make one numeric key descending while another stays ascending, negate the number:

sorted(students, key=lambda s: (-s[1], s[0]))
# [('ann', 92), ('bo', 85), ('cy', 85)]   score high to low, then name A-Z

Negation only works for numbers. When the descending key is a string, use two stable passes as above, with reverse=True on the pass that needs it.

Cost

Sorting n items takes roughly n log n comparisons in general, which is fast: a million numbers sort in a fraction of a second. Timsort is also adaptive: data that is already sorted, or made of sorted runs, sorts in close to linear time. The key function runs exactly n times.

Common mistakes

Using the result of sort(). nums = nums.sort() throws away your list and leaves None. Then nums[0] gives TypeError: 'NoneType' object is not subscriptable.

Calling the key function. sorted(words, key=len()) raises TypeError: len() takes exactly one argument (0 given). Pass len, not len().

Sorting numbers stored as text. sorted(["10", "9"]) gives ['10', '9']. Use key=int or convert first.

Case surprises. Uppercase sorts before lowercase. Use key=str.lower.

Negating strings. key=lambda r: -r[0] on a string raises TypeError: bad operand type for unary -: 'str'. Use two passes with reverse=True.

Recap

• sorted(iterable) returns a new list; list.sort() reorders in place and returns None.
• Elements are compared with <: numbers numerically, strings by code point, tuples element by element.
• key=func sorts by func(element), computed once per element; reverse=True sorts descending.
• lambda args: expression is a small inline function, ideal for keys.
• The sort is stable: ties keep their order, which enables multi-pass sorts. Tuple keys sort by several criteria; negate numbers for descending.

Going further: read the official "Sorting Techniques" HOWTO in the Python documentation, and look at operator.itemgetter and operator.attrgetter, which build common key functions for you.