Multi-key sorting in Python

Why this matters

Real data has more than one field. A list of students has a name and a grade. A list of orders has a customer and a date. People expect the list in a certain order, such as highest grade first, and within each grade, names from A to Z. A plain sort by one field does not give that. Students with the same grade come out in whatever order they started in.

This lesson shows two ways to get the combined order in Python. The first uses one key that is a tuple of fields. The second uses two stable sorts, one for each field. You will also see what goes wrong when the steps are in the wrong order, and how to handle missing values.

The sorting lessons before this one covered how a key works and what stability means. Heap sort, the previous lesson, is not stable. The sorts in this lesson are.

The idea: a primary key and a secondary key

A key is the value that a sort compares for each item. The primary key decides the main order. The secondary key only matters when two items have the same primary key.

Take five students. Each one has a name and a grade:

Zoe 82, Asha 91, Ravi 82, Bea 91, Tomas 70

The goal is this order: grade from high to low, and when two grades are equal, name from A to Z. The primary key is the grade, sorted high to low. The secondary key is the name, sorted A to Z.

Here is the result you want:

Asha 91, Bea 91, Ravi 82, Zoe 82, Tomas 70

Asha and Bea both have 91. Asha comes first because A comes before B. Ravi and Zoe both have 82. Ravi comes first because R comes before Z. Tomas has the only 70, so he is last.

Each record in the examples below has two fields, name and grade. The examples use dataclasses, which are short classes that hold fields and print readably. The class is called Student.

Example 1: one tuple key

A tuple is a fixed group of values written in parentheses, such as (91, "Asha"). Python compares two tuples one item at a time, from the left. The second item is looked at only when the first items are equal. That is exactly the rule for a primary and a secondary key.

To get "grade high to low, then name A to Z", the key needs the grade with a minus sign, because a bigger grade must come first, and the name as it is:

key = lambda s: (-s.grade, s.name)

The minus sign turns a bigger grade into a smaller number, so the sort puts it first. The name has no minus sign, because text cannot be negated, and the name is already compared A to Z.

The next program runs the tuple key on the five students. It also runs two sorts that use separate steps, which Example 2 explains. The students are built in, so you can run it without typing input.

The output is:

input: [('Zoe', 82), ('Asha', 91), ('Ravi', 82), ('Bea', 91), ('Tomas', 70)]
combined: [('Asha', 91), ('Bea', 91), ('Ravi', 82), ('Zoe', 82), ('Tomas', 70)]
after name sort: [('Asha', 91), ('Bea', 91), ('Ravi', 82), ('Tomas', 70), ('Zoe', 82)]
after grade sort: [('Asha', 91), ('Bea', 91), ('Ravi', 82), ('Zoe', 82), ('Tomas', 70)]

The combined line is the result you wanted. Read it as one pass. For each pair of students, Python first looks at the negated grade. Only when the grades match does it look at the name.

The sorted function returns a new list, so the students list stays as it was. Each sort starts from the same input. The list.sort() method changes the list it is called on, so the example uses sorted to keep the input for the next line.

Reading a key out loud

A long key is easier to check when you read it as a sentence. Read (-s.grade, s.name) like this: "compare by grade, bigger first, and then by name from A to Z." Each part of the tuple is a step, and each step answers one question about the two items.

When you write a key, ask for each step: which field is it, and which direction is it? If the answer to the second question is "high first", the step needs a minus sign, when the field is a number. If it is "A to Z" or "low first", it needs nothing. Checking each step this way catches most direction mistakes before the program runs.

Example 2: two stable sorts

A stable sort keeps items that compare as equal in the order they had before the sort. Python's sorted and list.sort are stable. This is the property that makes the second method work.

The idea is to sort twice. First sort by the secondary key. Then sort by the primary key. The second sort moves whole groups, but it keeps the order inside each group, because the sort is stable.

Look at the two lines after the name sort and after the grade sort:

after name sort: Asha 91, Bea 91, Ravi 82, Tomas 70, Zoe 82
after grade sort: Asha 91, Bea 91, Ravi 82, Zoe 82, Tomas 70

After the name sort, the list is in name order: Asha, Bea, Ravi, Tomas, Zoe. The grade sort then puts the 91s first, then the 82s, then the 70. Inside the 91 group, Asha still comes before Bea, because a stable sort does not reorder equal items. Inside the 82 group, Ravi still comes before Zoe. The result is the same as the tuple key.

The grade sort uses reverse=True to put the high grades first. Python's reverse=True keeps equal items in their current order, so the names still stay in order inside each grade. This is a useful fact: reverse=True does not flip the order of ties.

Use two stable sorts when the keys come from different places. For example, the list may already be sorted by name from a database, and you only need to add a sort by grade. A stable sort keeps the name order inside each grade. The cost is a second pass over the list, which is small for normal list sizes.

Example 3: two fields that point in different directions

The rules for one key can differ from the rules for the other. A common request is "city from A to Z, and within each city, youngest first". The field city sorts A to Z, and age sorts from low to high. Both are ascending, so no minus sign is needed.

Here is the same idea on tuples, with a tuple key that uses the city and the age:

The output is:

city A to Z, age youngest first: [('Delhi', 22), ('Delhi', 40), ('Pune', 25), ('Pune', 30)]
city Z to A, age youngest first: [('Pune', 25), ('Pune', 30), ('Delhi', 22), ('Delhi', 40)]

The first line is the rule you asked for. Delhi comes before Pune. Inside Delhi, the age 22 comes before 40.

The second line uses two stable sorts. The first sort puts the ages in order, from youngest to oldest. The second sort, by city with reverse=True, puts Pune before Delhi and keeps the age order inside each city. Only the city step is reversed, and the age order is the same in both lines.

When the city is text and you want it reversed inside one tuple key, a minus sign does not work. That is why the second line uses two sorts. For numbers, the minus sign is the shorter choice.

Keys that can be missing

A key can be missing. A student may have no nickname, which in Python is the value None. Comparing None with a text value raises an error, so the key needs a rule for it. A common rule is a tuple whose first item is True or False. The item x is None is True for a missing value, and False sorts before True, so the names go first. The second item gives the real value, or an empty text for a missing one, so that the comparison never sees None.

The output is:

nulls last: ['Amy', 'Bo', 'Zed', None, None]
nulls first: [None, None, 'Amy', 'Bo', 'Zed']

The expression x or "" gives x when x is a real name, and an empty text when x is None. In the first line, a missing value gets the key (True, ""), which is larger than every (False, name), so it goes last. In the second line, the key for a missing value is (False, ""), which is smaller than every (True, name), so it goes first.

Example 4: three keys

The same steps work with more than two keys. Take a list of sales, each with a region, a product and a number of units. The wanted order is region from A to Z, then units from high to low inside each region, then product from A to Z when the units are equal.

Each key is one part of the tuple. The units part gets its own minus sign, so only that part is flipped. The product part is last, so it only breaks ties that remain after the region and the units are compared.

The output is:

East 30 Coffee
East 30 Tea
East 5 Cocoa
West 40 Coffee
West 12 Cocoa
West 12 Tea

Look at the two East rows with 30 units. Both have the same region and units, so the product decides. Coffee comes before Tea. The two West rows with 12 units follow the same rule, so Cocoa comes before Tea.

The loop for region, product, units in sorted(...) unpacks each tuple into three names. The sort itself returns the sales in order, and the loop prints them.

Which method to choose

Both methods give the same result when they are written correctly. They differ in how easy they are to read, and in what can go wrong.

The tuple key does one sort. The whole rule is in one place, so a reader can see every key and its direction at once. The risk is a missing minus sign on a number, or a text key that needs a reversed direction. Test the output with a small list that has ties in every key, so a wrong direction shows up.

Two stable sorts make each sort very simple. Each one checks a single field. This is useful when the list is already sorted by one key, for example when a database returns rows in date order, and you only need to sort by another field. The cost is one pass for each key. The risk is the order of the calls. With three keys, you must sort by the last key first and the first key last. Writing that down in a comment helps.

For a rule with three or more keys, a tuple key is usually easier to read. For a list that is already partly sorted, two stable sorts can be shorter. In both cases, print a small example and check the result by eye before you trust it.

Common mistakes

Doing the two stable sorts in the wrong order

The two-sort method works only when the secondary key is sorted first. If you sort by the primary key first, the second sort, which is on the secondary key, breaks the grade groups. Here is the wrong order:

Its output is:

wrong order of stable sorts: [('Asha', 91), ('Bea', 91), ('Ravi', 82), ('Tomas', 70), ('Zoe', 82)]

The list is now in name order. The grade is no longer the main key, and the 70 sits between two 82s. Nothing crashes, so a quick look at the output is the only way to catch this bug. Remember the rule: sort by the secondary key first, and the primary key last.

Putting the minus sign or reverse on the whole key

A reverse=True on a tuple key flips every part of the key, including the name. In this program, the grade and the name are both reversed:

The output is:

reversed at the end: [('Bea', 91), ('Asha', 91), ('Zoe', 82), ('Ravi', 82), ('Tomas', 70)]

The grades are right, but the names inside each grade now run from Z to A. Bea comes before Asha, and Zoe comes before Ravi. To flip only the grade, put the minus sign on the grade part, as in (-s[1], s[0]), or use two stable sorts.

Using a minus sign on text

A minus sign works only on numbers. This key tries to reverse the name, and Python refuses:

The output is:

Traceback (most recent call last):
  File "minus.py", line 2, in <module>
    print(sorted(students, key=lambda s: (s[1], -s[0])))
          ~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "minus.py", line 2, in <lambda>
    print(sorted(students, key=lambda s: (s[1], -s[0])))
                                                ^^^^^
TypeError: bad operand type for unary -: 'str'

The file paths and line numbers in these tracebacks depend on where you saved the files. The last line says the minus sign has no meaning for a string. For a text field in reverse order, use two stable sorts, with reverse=True on the text sort, or sort the text first and the number last.

Sorting a tuple in place

Tuples cannot change, so they have no sort method. The method list.sort works only on lists. Use sorted, which returns a new list from any iterable, or convert the tuple first with list(...).

The output is:

Traceback (most recent call last):
  File "tuple_sort.py", line 2, in <module>
    t.sort()
    ^^^^^^
AttributeError: 'tuple' object has no attribute 'sort'

The fix is sorted(t), which returns the list ['a', 'b'] and leaves t unchanged.

Comparing a missing value

Without a rule for None, a missing value makes the comparison fail. This code sorts a list with one missing value, and no key handles it:

The output is:

Traceback (most recent call last):
  File "none.py", line 2, in <module>
    print(sorted(names))
          ~~~~~~^^^^^^^
TypeError: '<' not supported between instances of 'NoneType' and 'str'

The message says the < comparison met None, which is a NoneType, and a string. Use the key from the missing-values section to decide where the missing values go.

Practice

Try each exercise in a file first. Check your answer after you have made an attempt.

Exercise 1: longest words first

Sort these words so the longest comes first. Words with the same length should come in alphabetical order: kiwi, fig, apple, date, pear. The expected result is ['apple', 'date', 'kiwi', 'pear', 'fig'].

Show the answer

Use the negated length as the primary key, and the word itself as the secondary key:

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

The minus sign on the length flips only the length. The words date, kiwi and pear all have 4 letters, and they come out in alphabetical order. This code was run and printed ['apple', 'date', 'kiwi', 'pear', 'fig'].

Exercise 2: why the grade-first method fails

Explain in plain words why sorting by name first and then by grade gives the right answer, but sorting by grade first and then by name does not.

Show the answer

A sort moves items to a new order based on its key. A stable sort keeps equal items in their earlier order. When you sort by name first, the list is in name order. When you then sort by grade, equal grades keep their name order, so the names stay sorted inside each grade. When you sort by grade first and then by name, the second sort undoes the grade order, because it moves items by name and does not look at grades at all.

Exercise 3: missing values first

Sort the list ["b", None, "a"] so that the missing value comes first, then the names from A to Z.

Show the answer

Use a key whose first item is False for a missing value. The missing value then sorts before every real name:

values = ["b", None, "a"]
print(sorted(values, key=lambda x: (x is not None, x or "")))

The result is [None, 'a', 'b']. This code was run and printed that result.

Exercise 4: city Z to A, age youngest first

Use the same four people from Example 3. Sort them so the city goes from Z to A, and inside each city the youngest comes first.

Show the answer

Sort by age first, then sort by city with reverse=True. The second sort keeps the age order inside each city:

people = [("Pune", 30), ("Delhi", 40), ("Pune", 25), ("Delhi", 22)]
result = sorted(sorted(people, key=lambda p: p[1]), key=lambda p: p[0], reverse=True)
print(result)

The result is [('Pune', 25), ('Pune', 30), ('Delhi', 22), ('Delhi', 40)]. This code was run and printed that result.

Exercise 5: find the bug

A student wants a list sorted by grade, highest first, and then by name from A to Z. They wrote this:

students.sort(key=lambda s: (s.grade, s.name), reverse=True)

They say the names are backward. Why, and how do they fix it?

Show the answer

The reverse=True flips the whole tuple, so the grade and the name are both reversed. The grades come out highest first, which is what they want, but the names come out from Z to A. The fix is to put the minus sign on the grade only: students.sort(key=lambda s: (-s.grade, s.name)). The name is then compared from A to Z.

Summary

• A primary key decides the main order. A secondary key breaks ties.
• A tuple key compares its items from the left. The second item is looked at only when the first items are equal.
• A minus sign reverses a number. Text cannot be negated, so reverse a text field with reverse=True in a separate stable sort.
• Two stable sorts also work. Sort by the secondary key first, then by the primary key.
• reverse=True on a whole key flips every part of it. To flip one number only, use a minus sign on that part.
• Use a key with a True or False first item to decide where missing values go, and sort a tuple with sorted rather than .sort.