Python Sorting

3Python Sorting: explained step by step

Sorting means putting items in order: scores from high to low, names from A to Z, tasks from most to least urgent. Python gives you two tools for it, and the difference between them causes more confusion than the sorting itself.

sorted() builds a new list

sorted() accepts any collection and returns a new list with the items in order. The original is not touched, so it is safe to use anywhere.

scores = [72, 95, 88, 61]
ranked = sorted(scores)
print(ranked)
print(scores)

Because it accepts any iterable, sorted() also works on tuples, sets, strings and dictionary keys. The result is always a list: sorted("python") gives a list of single letters, not a string.

list.sort() changes the list itself

my_list.sort() rearranges the list in place and returns None. It does not build a second list, but only lists have it and the old order is gone for good.

scores = [72, 95, 88, 61]
result = scores.sort()
print(scores)
print(result)

A good rule: use .sort() on a list you own and no longer need in the old order, and use sorted() when you must keep the original or when the data is not a list. Never write scores = scores.sort(), because that replaces your list with None.

Descending order, and why reversed() is different

Pass reverse=True to either tool to get the largest value first. Do not confuse it with reversed(), which does no comparing at all: it just walks the items backwards from whatever order they are already in, and gives you an iterator to wrap in list().

scores = [72, 95, 88, 61]
print(sorted(scores, reverse=True))
print(list(reversed(scores)))

Strings: capital letters and numbers written as text

Text is compared one character at a time using each character's code. Every capital letter has a smaller code than every lowercase letter, so "Zoe" comes before "adam". Digits are characters too, so "10" comes before "9": Python sees that "1" is smaller than "9" and stops there.

names = ["maya", "Zoe", "adam", "Ben"]
print(sorted(names))
print(sorted(names, key=str.lower))

ids = ["10", "9", "100", "2"]
print(sorted(ids))
print(sorted(ids, key=int))

Both fixes use the same tool, key=.

key=: choose what to compare

key takes a function. Python calls it once for every item, sorts by the values it returns, and then hands back the original items. The diagram above shows key=len: the words are ranked by their lengths, but you still get words.

words = ["pear", "fig", "banana", "kiwi"]
print(sorted(words, key=len))
print(sorted(words, key=lambda w: w[-1]))

A lambda is a tiny function written on one line: lambda w: w[-1] means "given w, return its last letter". A normal def function works in key= just as well. Always pass the function itself (key=len), never a call (key=len()).

Sorting tuples, records and dictionaries

Tuples are compared by their first item, then by the second when the first ties. To sort by a different position, pass a key. operator.itemgetter builds a key function that picks out one position or one dictionary key, and it is shorter than a lambda.

from operator import itemgetter

orders = [("tea", 3.5), ("cake", 4.0), ("coffee", 2.5)]
print(sorted(orders))
print(sorted(orders, key=itemgetter(1)))

students = [
    {"name": "Asha", "score": 82},
    {"name": "Ben", "score": 91},
    {"name": "Cara", "score": 77},
]
best_first = sorted(students, key=itemgetter("score"), reverse=True)
for student in best_first:
    print(student["name"], student["score"])

The students are dictionaries, records that store named fields as key: value pairs (the dictionary lessons come next). For objects, operator.attrgetter("score") does the same job for attributes.

A dictionary cannot be sorted in place, but you can sort its pairs and build a new dictionary, which remembers that order:

from operator import itemgetter

stock = {"apples": 12, "pears": 0, "plums": 7}
print(sorted(stock))
by_count = dict(sorted(stock.items(), key=itemgetter(1), reverse=True))
print(by_count)

sorted(stock) on its own sorts the keys only; stock.items() gives you the (key, value) pairs to rank.

Sorting by several things at once

When the key function returns a tuple, Python compares the first part, and only looks at the next part if the first ones tie. A minus sign flips a number, so one part can run high to low while the other runs A to Z:

players = [("Ben", 90), ("Asha", 90), ("Cara", 75), ("Dev", 82)]
print(sorted(players, key=lambda p: (-p[1], p[0])))

Highest score first, and players on the same score in alphabetical order. The minus trick only works for numbers.

Stability

Python's sort is stable: items with equal keys keep the order they had before. That makes ties predictable, and it gives you a way to mix directions on text. Sort by the less important rule first, then by the main rule:

players = [("Ben", 90), ("Asha", 90), ("Cara", 75), ("Dev", 82)]
step1 = sorted(players, key=lambda p: p[0], reverse=True)
step2 = sorted(step1, key=lambda p: p[1])
print(step2)

Step 1 puts the names in Z to A order. Step 2 sorts by score, low to high, and because it is stable the two 90s stay in Z to A order.

min() and max() take key too

If you only need the best or the worst item, don't sort the whole list. min() and max() accept the same key=, and default= covers an empty collection:

from operator import itemgetter

cart = {"pen": 1.5, "lamp": 24.0, "mug": 6.0}
print(max(cart, key=cart.get))
print(min(cart.items(), key=itemgetter(1)))
print(max(["kiwi", "banana", "fig"], key=len))
print(max([], default="empty"))

Items must be comparable

Sorting works by asking "is this item smaller than that one?". Numbers and text cannot answer that question for each other, so mixing them raises a TypeError. None is just as stubborn. Clean the data first, or use a key that turns every item into the same type.

mixed = [3, "2", 1]
try:
    sorted(mixed)
except TypeError as err:
    print(err)
print(sorted(mixed, key=int))