sorted(), key functions, cmp_to_key and stability in Python

Why this lesson matters

In real code, you almost never write a sorting algorithm. You call the built-in sort, and then you spend your effort on the rule that decides the order. "Sort the orders by delivery date, then by customer name" is a rule. Python knows how to sort. You have to tell it what "order" means.

Interviews work the same way. A common question is "merge overlapping time slots" or "rank the players by score, then by name." The answer starts with a sort, and the interesting part is the rule that decides the order. This lesson teaches the built-in sort, the key function, the comparator, the most common mistakes, and stability, which is the property that lets you sort in several steps and still get the right answer.

Sorting in one line

Python gives you two ways to sort, and both use the same method under the hood.

• sorted(items) returns a new list and leaves the original list unchanged.
• items.sort() changes the list in place and returns None.

nums = [5, 2, 9, 1]
print(sorted(nums))        # [1, 2, 5, 9], nums is still [5, 2, 9, 1]
nums.sort()                # nums is now [1, 2, 5, 9]

Both forms accept the same options. The option reverse=True sorts from biggest to smallest. Both forms also accept key=, a function that gives each item the value to compare. You will use key= in almost every real sort.

Python has no separate "primitive" arrays for sorting, so the rule that Java needs for int[] versus Integer[] does not apply here. Every list sort in Python is stable. The method is Timsort, which you met in the merge sort lesson. It is a merge-based method, it is stable, and it runs quickly on lists that are partly in order.

Both sorts take about n times log n time on typical data. The rest of this lesson is about the rule you give the sort.

What a comparator is, and what a key is

A comparator is a small rule that answers one question: given two items a and b, which one comes first? It returns a number.

• A negative number means a comes before b.
• Zero means they are equal for this rule.
• A positive number means b comes before a.

Think of two people standing in a queue. You ask, "who should stand in front?" and the answer is a sign: "a in front" is negative, "b in front" is positive, and "either is fine" is zero. The sort asks this question for many pairs of items and builds the full order from the answers.

A key function is a different tool for the same job. It takes one item and returns the value to sort by. The sort then compares the keys. Most rules can be written as a key, and a key is easier to read. Python's built-in sorts use keys, and the comparator form is kept for rules that cannot be written as one value per item.

words = ["pear", "fig", "apple", "kiwi", "plum"]
 
print(sorted(words, key=len))                      # shortest first
print(sorted(words, key=lambda w: (len(w), w)))    # shortest first, then alphabetical
print(sorted(words, key=len, reverse=True))        # longest first

The lambda in the second line is a short unnamed function. lambda w: (len(w), w) takes a word and returns a pair. Python compares pairs by their first item, and uses the second item only when the first items are equal. That is how a second rule works without any extra code.

The first line sorts by one rule. Three words have length 4: pear, kiwi and plum. They keep their input order, which is pear, kiwi, plum. That is stability at work. The second line adds a tie-breaker, so the three four-letter words are in alphabetical order, kiwi, pear, plum.

Here are the same kinds of sorts on numbers, lists and tuples. The program has its data built in, so you can run it without typing input.

The output is:

[9, 5, 2, 1]
['fig', 'pear', 'kiwi', 'plum', 'apple']
['fig', 'kiwi', 'pear', 'plum', 'apple']
[[1, 3], [2, 6], [5, 8]]
['Bob', 'Zed', 'amy']
['amy', 'Bob', 'Zed']
[-1, 3, 5, -7]
[2, 4, 1, 3]

The line with key=str.lower shows a key that changes the value before the comparison. The string "amy" is compared as "amy", and "Zed" as "zed", so the capital letter no longer puts "Bob" and "Zed" ahead of "amy". The natural order of plain strings compares character codes, and capital letters have smaller codes than small letters. The line with key=abs sorts by distance from zero, so -1 comes before 3, and -7 comes last. The last line puts the even numbers first and the odd ones after, each group in ascending order, because x % 2 != 0 is False for even numbers and False sorts before True.

The key (x % 2 != 0, x) is a pair. The first item decides the group, and the second item sorts inside the group. That pattern works for any number of rules.

Records: small classes for data

Many sorts work on objects that hold more than one value, such as a student's name and grade. Python has a short way to write such a class, called a dataclass. The decorator @dataclass adds an __init__ method that takes each field, and a readable repr, which is the text that shows what an object holds.

from dataclasses import dataclass
 
@dataclass(frozen=True)
class Student:
    name: str
    grade: int

The line frozen=True makes the object unchangeable after it is created. That is a good habit for data that is only read. You read the fields with s.name and s.grade, as plain attributes. The dataclass does not give the class an order by itself, so a sort needs a key that says which field to use. The sort in the next section shows how.

Merging overlapping intervals

A classic interview problem gives a list of time blocks, such as meetings in a calendar, and asks you to merge the blocks that overlap. Two blocks overlap when one starts before the other ends. Blocks that only touch, where one ends exactly when the next starts, are merged too in the version this lesson uses.

The algorithm has two steps. First, sort the blocks by start time. After this, each block can overlap only with the block that follows it, or with the merged block in progress. Second, walk the sorted list. Keep the current merged block. If the next block starts after the current one ends, start a new merged block. If not, extend the current block's end to the larger of the two ends.

Walk the algorithm on [1, 3], [2, 6], [8, 10], [15, 18].

• Sorted by start, the list is the same: [1, 3], [2, 6], [8, 10], [15, 18].
• Start with [1, 3]. The next block [2, 6] starts at 2, which is not after 3, so it overlaps. Extend the end to max(3, 6), which is 6. The block is [1, 6].
• The next block [8, 10] starts at 8, which is after 6. Start a new block [8, 10].
• The next block [15, 18] starts at 15, which is after 10. Start a new block [15, 18].

The result is [1, 6], [8, 10], [15, 18]. The sort takes O(n log n) time, and the walk takes O(n). The total is O(n log n).

This function does the merge. It returns a new list and leaves the input alone, because the merged blocks are new lists.

The output is:

[[1, 6], [8, 10], [15, 18]]
[[1, 5], [6, 7]]

The second call shows the touching case. The blocks [1, 4] and [4, 5] touch at 4. The check merged[-1][1] >= start asks whether the current block still reaches the next one's start. Here 4 >= 4 is true, so the blocks merge. If you wanted touching blocks to stay separate, you would use > in that check. Decide this from the problem statement, and write the decision in a comment, because the two versions give different answers on the same input.

The loop unpacks each interval into two names with for start, end in .... Python does this for any sequence of two values, so you do not need to write iv[0] and iv[1] inside the loop. The merged list holds lists, so merged[-1][1] reads the end of the last block.

Sorting students by two rules

Now the key does real work. The next program sorts students by grade, highest first, and by name for ties. The rule is one key: the negative grade sorts the higher grades first, and the name breaks ties in alphabetical order.

The output is:

Kiran 91
Ravi 91
Asha 72
Meera 72
Dev 60

Read the key from left to right. -s.grade puts the bigger grade first, because a bigger grade has a smaller negative number. s.name breaks ties by name, in alphabetical order. Kiran and Ravi both have 91, so Kiran comes first. Asha and Meera both have 72, so Asha comes first.

The negative sign works only for numbers. A name cannot be negated, so a rule that needs one text key in reverse and one number in forward order needs a different approach. The next section shows the stable two-step method for that case. Python's reverse=True does reverse the whole key, and it keeps ties in input order too, so it is safe to use when all the keys go the same way.

The same rule can also be written as a comparator with functools.cmp_to_key. A comparator is useful when the rule is easier to write as a set of questions than as one value. Here is the same result with a comparator:

The output is:

['Kiran', 'Ravi', 'Asha', 'Meera', 'Dev']

The function cmp_to_key turns a comparator into a key, because the sort needs a key-like object. Inside the comparator, each branch returns a negative number, zero or a positive number. The subtraction b.grade - a.grade is safe here, and the section on comparator traps explains why it is safe in Python.

For most rules, the key form is shorter and clearer. Use the comparator when the rule has many branches, or when the question is about two items at once and cannot be turned into one value for each item.

Stability: why the order of ties matters

A sort is stable when items that compare as equal keep their original relative order. If two students both have grade 72, and Asha is listed before Meera in the input, a stable sort keeps Asha before Meera in the output.

This sounds like a small detail, but it is the key to sorting in several steps. Suppose you want the list sorted by grade, and inside each grade the names in alphabetical order. One way is one key with two rules, as in the last program. Another way is two separate sorts. First sort by name. Then sort by grade. Because the second sort keeps ties in their current order, the names stay alphabetical inside each grade. This works only if the sort is stable, and Python's sort always is.

Here is that process on four students. The input lists them in this order:

before:               Asha(B)  Ravi(A)  Meera(B)  Dev(A)
sort by name:         Asha(B)  Dev(A)   Meera(B)  Ravi(A)
stable sort by grade: Dev(A)   Ravi(A)  Asha(B)   Meera(B)

Walk through the second step. The list before it is Asha(B), Dev(A), Meera(B), Ravi(A). A stable sort by grade, with A before B, puts the two A students first, in the order they had: Dev before Ravi. Then the two B students, in their order: Asha before Meera. The result is alphabetical inside each grade, and the grades are in order.

An unstable sort might give Ravi(A), Dev(A), Meera(B), Asha(B) in that second step, which breaks the name order. Only a stable sort gives the reliable answer in the two-step method. Python guarantees stability, so the two-step method is safe here.

The next program runs the two-step method on the same four students. It also prints the output of the one-key version, so you can compare them.

The output is:

[('Dev', 'A'), ('Ravi', 'A'), ('Asha', 'B'), ('Meera', 'B')]
[('Dev', 'A'), ('Ravi', 'A'), ('Asha', 'B'), ('Meera', 'B')]

Both methods give the same answer, because the sort is stable. The grade A comes before B in both, and the names inside each grade are in alphabetical order.

Python's reverse=True also keeps ties in input order. That is different from reversing a comparator in some languages, where the ties can come out reversed. The next program checks it on a small list.

The output is:

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

The two items with key 1 are a and c. They keep their input order, so a comes before c. That is the behaviour a stable sort gives.

Comparators that look right and are not

Python integers have no size limit, so the classic comparator bug of subtracting two numbers that overflow a fixed-size integer does not happen here. The next program shows a value that would overflow a 64-bit long in Java:

The output is:

-9223372036854775809
True

The subtraction gives the exact answer, because Python makes a bigger integer when it needs one. A comparator that returns a - b is therefore correct for every pair of Python ints. That is not true for every language, so the habit of using a compare function is still good when the same code moves to Java, C or another language with fixed-size integers.

A different trap does exist in Python. A comparator must return a number, but a comparison such as a > b returns True or False. Python treats True as 1 and False as 0, so a boolean is never negative, and the sort never sees "a comes first." The sort does not raise an error. It returns the list in an order that is not sorted:

The output is:

[3, 1, 2]

The list is unchanged, and no error was raised. The comparator said "a is bigger" only as 1 or 0, which is never a "come first" answer. The fix is to return a negative number for "a comes first," which is what (a > b) - (a < b) does. That expression gives 1 when a is bigger, -1 when a is smaller and 0 when they are equal. For numbers, a - b also works.

Writing a key from a rule in words

Interviewers often describe the order in words, and your task is to translate the words into a key. Here is a rule: sort the orders by city from A to Z, then by price from highest to lowest, then by order id from smallest to largest. Translate each phrase in the order it appears.

• "by city from A to Z" becomes the first item in the tuple, o.city. Text sorts alphabetically, so no negation is needed.
• "then by price from highest to lowest" becomes -o.price. A bigger price has a smaller negative number, so it comes first.
• "then by order id from smallest to largest" becomes o.id.

The full key looks like this:

orders.sort(key=lambda o: (o.city, -o.price, o.id))

Check the key against the rule, one phrase at a time. The most common mistake is to put reverse=True on the whole sort, which would reverse the city order too. The second common mistake is to negate the city, which fails because text cannot be negated. Reading the key aloud, one item per phrase, catches both.

Take three orders to check the key by hand. The orders are ("Pune", 500, 3), ("Delhi", 900, 1) and ("Pune", 900, 2), written as city, price and id. The city step puts Delhi first, then the two Pune orders. Inside Pune, the price step puts 900 before 500, so order 2 comes before order 3. The result is Delhi 900 (id 1), Pune 900 (id 2), Pune 500 (id 3). Your code should print these three in that order, and a wrong key shows at once in a three-item test like this.

The next program runs that check:

The output is:

[('Delhi', 900, 1), ('Pune', 900, 2), ('Pune', 500, 3)]

A worked example: stability in a two-step sort

The stability section described a two-step sort. Here is the same process in the form an interviewer may ask about, with every step written out. Sort four students, first by name, then by grade, and keep the names in order inside each grade.

Input in input order: Asha B, Ravi A, Meera B, Dev A. The letter is the grade.

• Step 1, sort by name, A to Z. The names are Asha, Dev, Meera, Ravi. The list is Asha B, Dev A, Meera B, Ravi A.
• Step 2, stable sort by grade, A before B. The A students are Dev and Ravi. In the current list, Dev comes before Ravi, so a stable sort keeps Dev first. The B students are Asha and Meera. Asha comes before Meera, so they keep that order. The result is Dev A, Ravi A, Asha B, Meera B.

Now the same two steps with an unstable second sort. The first step gives the same list. The second sort might move Ravi in front of Dev, because they are equal under the grade rule and an unstable method may swap them. The result would then be Ravi A, Dev A, Asha B, Meera B, and the names inside grade A would no longer be in alphabetical order. The two-step method is correct only because the second sort keeps ties in place.

Python's sorts are stable, so this two-step method is safe in Python. You still need to know it, because it is a common idea in data work: you can sort by one column and then by another, and the first sort's order survives the second.

Debugging a comparison that changes the answer

Here is a bug in the interval merge from this lesson, and it shows how a small change alters the answer. The code tests whether the current block still reaches the next one's start, using >=. Someone rewrites it with >, thinking the two are the same, and the outputs change for one input.

Start with the input [[1, 4], [4, 5], [6, 7]]. The blocks [1, 4] and [4, 5] touch at 4. With the original >= check, 4 >= 4 is true, so the blocks merge into [1, 5], and the output is [[1, 5], [6, 7]]. With the rewritten > check, 4 > 4 is false, so the code starts a new block, and the output is [[1, 4], [4, 5], [6, 7]]. Both programs print sorted blocks. Only a test with touching blocks shows that they differ.

The next program runs the rewritten version so you can see the output:

The output is:

[[1, 4], [4, 5], [6, 7]]

The lesson is about tests, not about which answer is right. Before you change a comparison, decide what the problem means, write that decision in a comment, and add one test for the case the change affects. In this problem, a meeting that ends at 4 and another that starts at 4 do not overlap, so the decision could be > for "separate blocks". The lesson's program merges touching blocks, which is a different decision. Both are valid, but you must choose one on purpose.

Variations you will use

Some orders come up again and again, and each one is a short change to the same pattern.

• Sort by absolute value, so -5 comes before 3: sorted(a, key=abs).
• Sort a dictionary's items by value: sorted(d.items(), key=lambda kv: kv[1]), or with reverse=True for the highest value first. You will meet dictionaries in a later module.
• Sort rows of a list of lists by one column, then by another column: sorted(rows, key=lambda r: (r[0], r[1])).
• Sort strings ignoring case: sorted(words, key=str.lower). The key changes each word only for the comparison, and the output keeps the original capitals.

When you meet a new order, first name the key, then decide on the direction, then decide the tie-breaker. Those three decisions match the three parts of the key tuple.

Choosing a sort in an interview

The table below is a checklist you can use when a question asks for sorting.

Name the choice and the reason. A good answer to "how would you sort these?" says, "I would use sorted with a key on the start time, because it is O(n log n) and I need the blocks in order." A weaker answer only names a method. Interviewers want the reason.

Common mistakes and their messages

Mistake 1: sorting objects with no order. A list of dataclass objects has no default order, so sorted(students) fails. This program shows the message:

The output is:

Traceback (most recent call last):
  File "objects.py", line 9, in <module>
    print(sorted(students))
          ~~~~~~^^^^^^^^^^
TypeError: '<' not supported between instances of 'Student' and 'Student'

The last line says the < comparison has no meaning for Student objects. The fix is a key, as in sorted(students, key=lambda s: s.grade), which tells the sort which field to compare. The first path depends on where you saved the file.

Mistake 2: mixing types in one sort. A list that holds numbers and text cannot be sorted, because the comparison has no meaning for both. The message is the same kind as in the first lesson: TypeError: '<' not supported between instances of 'str' and 'int'. The fix is to make the key return one type for every item.

Mistake 3: expecting sort() to return a new list. list.sort() changes the list and returns None. A line such as result = nums.sort() leaves result as None. Write nums.sort() and then use nums, or write result = sorted(nums) to keep the original.

Mistake 4: a boolean comparator. Covered above, the bug gives no error. A comparator that returns a > b returns only 1 or 0, so the list is not sorted, and the output looks like a plausible order for small inputs. The fix is to return a negative number, for example (a > b) - (a < b).

Mistake 5: negating text. A key such as -s.name fails, because a string cannot be negated:

The output is:

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

The message says the minus sign works only on numbers. For text in reverse order, use reverse=True on a sort that has only text keys. For a mixed rule, use two stable sorts, the method from this lesson.

Mistake 6: putting reverse=True on the whole key. With a key like (o.city, -o.price), reverse=True would reverse the city order too. Use the minus sign on the number only, or use two stable sorts.

Debugging walkthrough

Here is a sort that fails in a quiet way. The goal is to sort students by grade, highest first. The code uses a key on the grade, but the order is wrong.

students.sort(key=lambda s: s.grade)

Run it on the input Asha 72, Ravi 91, Meera 72, Dev 60, Kiran 91. The output is ascending by grade, lowest first. The task asked for highest first. The fix is reverse=True, or key=lambda s: -s.grade. That is the same trick as the descending example earlier, and it is the first thing to check whenever the order is reversed.

Now suppose the order is right, but the ties come out in a surprising order. The output shows Meera before Asha, although Asha was first in the input. Check two things. First, is the sort one that Python guarantees to be stable? Python's sorted and list.sort are stable, so the cause is somewhere else. Second, does the key use only the grade? If the key is (s.grade, s.name), the names break the ties, and the output looks different from the input order on purpose. A key like s.name alone would reorder the students by name, not by grade, which is the wrong rule.

Use the same method as in the earlier lessons:

1. Pick a small input with two equal values and label them with their input order.
2. Write the key for each item by hand.
3. Compare the keys. A smaller key comes first, and equal keys keep input order.
4. Only then run the program, and compare the output with your prediction.

Variations and edge cases

• None values. If some objects might be None, a plain key crashes on them, because None cannot be compared with a number. Put a key that handles None first, such as key=lambda s: (s.grade is None, s.grade or 0).
• Reverse one rule only. Use a negative number for the rule you want reversed, as in (-s.grade, s.name). Using reverse=True would reverse the names too.
• Strings ignoring case. key=str.lower is a ready-made key for this.
• Sorting characters. sorted("banana") returns a list of single characters, ['a', 'a', 'a', 'b', 'n', 'n']. The order is by character code, so capital letters come before small ones.
• Sorting part of a list. Python has no range argument for sort. Take the part you need with a slice, sort it, and put it back: a[1:3] = sorted(a[1:3]).
• Empty lists. sorted([]) returns an empty list, and no key function is called. The merge function in this lesson also handles an empty list, because its first check is merged and ....

Testing a comparator

A comparator is a small rule, and a small rule can be wrong in ways that a single example does not show. Two properties catch most mistakes. The first is that the answer flips when the arguments are swapped: compare(a, b) and compare(b, a) must have opposite signs, or both be zero. The second is that the rule is consistent across three items: if a comes before b, and b before c, then a must come before c. A comparator that breaks either property can give an order that depends on the input order.

Write a check for the first property, and run it on a few pairs, including equal ones and extreme values. The check below uses the boolean comparator from the trap section and a correct one:

The output is:

good bad pairs: 0
boolean bad pairs: 12

The boolean comparator fails this check, with 12 bad pairs. For two different values, it returns True in one direction and False in the other, and those two answers do not have opposite signs. A test should also check the sort's result on a small list, as the trap section did, because the sign check alone does not show the wrong order on its own.

The second property is harder to test by hand, so test it with the sort itself. Sort a list of records with your key or comparator, then sort it again in a different input order, and check that the two results are equal when all the keys are distinct. If they differ, the rule is not a total order, and the output depends on the input order.

Interview questions

Question: How do you sort intervals so that overlapping ones are next to each other? Answer: sort by start time, using a key on the first value. After that, a single walk can merge all the overlaps in O(n) time. The total is O(n log n), dominated by the sort.

Question: Why does a comparator that returns a > b give a wrong order? Answer: the comparison returns True or False, which Python reads as 1 or 0. A comparator must return a negative number for "a comes first," and this one never does, so the sort does not get the answer it needs. The fix is to return (a > b) - (a < b) or to use a key.

Question: Your two-step sort (by name, then by grade) gives the wrong answer. What do you check? Answer: check that the second sort is stable. Only a stable sort keeps the names in alphabetical order inside each grade. Python's sorts are stable, so look at the key of the second sort, which should use the grade only.

Question: When would you write your own key or comparator instead of using the natural order? Answer: when the order is not the default one, such as descending, by length, or by several fields. A good answer names the rule in plain words, then writes it as a key tuple.

Question: Your key function is correct on ten items but slow on a million. What do you look at first? Answer: look at what the key does on each call. A key that parses a string, reads a file or builds a new object does that work once per item. In a comparator the same work would run about n log n times, so the cost multiplies. Precompute the key once, store it in a field or a list, and let the sort read stored values. Python's key= form already calls the key once per item, not once per comparison, which is one reason to prefer it over a comparator.

Question: Write a sort that puts the even numbers first, then the odd ones, each group in ascending order. Answer: sorted(nums, key=lambda x: (x % 2 != 0, x)). The first part of the key is False for even numbers and True for odd ones, and False sorts first. The second part sorts inside each group. A strong answer checks the rule on a tiny list, such as [3, 4, 1, 2], which should become [2, 4, 1, 3].

Real-world uses

Calendar apps merge busy blocks, and a meeting room booking system uses the same interval merge to show free time. Ranking tables, such as game leaderboards, sort by score and then by the time the score was reached, which is a two-part key. Online stores sort products by price with a key on a record that holds the price, the rating and the date. Logs are sorted by timestamp, and stability keeps events that happened in the same second in the order they were written.

Practice

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

1. Sort ["banana", "kiwi", "apple"] by length, then print the result. Predict the output before you run it.

Show the answer

The lengths are 6, 4 and 5, so the order is kiwi (4), apple (5), banana (6). The output is ['kiwi', 'apple', 'banana'].

2. Sort [[3, 1], [1, 5], [3, 0]] by the first value, then by the second.

Show the answer

pts = [[3, 1], [1, 5], [3, 0]]
pts.sort(key=lambda p: (p[0], p[1]))

The result is [[1, 5], [3, 0], [3, 1]]. The first value 3 appears twice, and the second value breaks the tie.

3. Why does a stable sort matter when you sort a list of cities by city and then by country?

Show the answer

If the first sort is by city and the second by country with a stable sort, the cities stay in alphabetical order inside each country. An unstable second sort could mix them up. This is the two-step method from this lesson.

4. Write a key that sorts strings by length, longest first, and then alphabetically for ties. Explain why key=lambda s: len(s) - len(s) would not work.

Show the answer

sorted(words, key=lambda w: (-len(w), w)) puts the longer string first, and the alphabetical order breaks ties. The expression len(s) - len(s) is always 0, so every item has the same key and the sort changes nothing. The minus sign has to be applied to the length, not to a difference of the same value.

5. The key lambda iv: iv[0] is used on [[5, 8], [1, 3], [1, 2]]. Predict the order of the two intervals that start at 1, then check.

Show the answer

The sort is stable, so [1, 3] stays before [1, 2], because [1, 3] came first in the input. The result is [[1, 3], [1, 2], [5, 8]].

6. Write a function can_attend_all(meetings) that returns False when any two meetings overlap, and True otherwise. Meetings are [start, end] lists.

Show the answer

def can_attend_all(meetings):
    meetings = sorted(meetings, key=lambda m: m[0])
    for i in range(1, len(meetings)):
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

After the sort, an overlap can only be with the previous meeting. The function runs in O(n log n).

7. Explain why Python's built-in sort does not need a separate version for numbers and for objects, while Java has int[] and Integer[] sorts.

Show the answer

Python does not have a separate fixed-size array of numbers for sorting. Every list holds references to objects, and the sort is stable for all of them. Java's primitive int[] stores the numbers directly, and Java chose a faster sort for them that is not stable. Equal plain numbers cannot be told apart, so that is safe in Java, and Python does not need the split.

8. Sort a list of Student dataclass objects by name, ignoring case.

Show the answer

students.sort(key=lambda s: s.name.lower())

The key takes the name of each object and makes it lowercase for the comparison only. The names in the list keep their capitals.

9. A key reads lambda s: s.grade - 50 on objects where grades can be 0 to 100. Is the sort correct? Explain.

Show the answer

The key shifts every grade by the same amount, so the order is the same as the order of the grades. The sort is correct. The subtraction is not what makes it correct, because the shift does not change the order. A reader may still prefer the plain s.grade key, which says what is meant.

10. Trace sorted(["Zed", "amy", "Bob"]) and explain the order.

Show the answer

The natural order compares characters by their codes. Capital letters have smaller codes than small letters, so "Bob" and "Zed" come before "amy". Within capitals, B comes before Z. The result is ['Bob', 'Zed', 'amy']. To get alphabetical order that ignores case, use key=str.lower.

What you now know

• sorted() returns a new list and list.sort() changes the list in place. Both are stable.
• A key function gives each item the value to compare. A key can be a tuple, which compares its parts in order.
• A comparator returns a negative number, zero or a positive number. Use functools.cmp_to_key to pass one to a sort.
• Negate a number in a key to reverse one rule, and use two stable sorts when the rules go in mixed directions with text.
• Sort intervals by their start, then walk the sorted list to merge overlaps.
• Stability keeps tied items in input order, which makes two-step sorts correct.
• A comparator that returns a boolean does not crash. It gives the wrong order, so return a negative number for "comes first."
• Read a Python traceback from the bottom line up. The last line names the error, such as TypeError for a missing order between objects.