Bad comparator bugs in Python

Why this matters

Say you have a list of students and want them sorted by score. Python needs a rule that answers one question for any two students: which one comes first? That rule is a comparison function, used with functools.cmp_to_key, or a key function, used with sorted(..., key=...). Most of them are one line long, and most of the time that line is fine. When it is wrong, the list may come back in the wrong order with no error at all. Python does not check the rules while it sorts, so there is no warning. The other bad outcome is a TypeError raised by a comparison that met a value it cannot compare, such as None.

This lesson covers the rules a comparison has to follow, five common ways code breaks them, and how to write the comparison so it stays correct. It builds on the lessons about keys and comparison contracts in this module. Here the focus is on what goes wrong when the comparison itself is faulty.

What a comparison function does

A comparison function answers one question about two items, a and b: which one should come first? It returns a number. The answer means the following.

• A negative number means a comes before b.
• Zero means the two are equal for sorting.
• A positive number means a comes after b.

functools.cmp_to_key turns such a function into a key that sorted understands. A lambda is a short function written inline, and lambda a, b: ... means "a function that takes a and b".

from functools import cmp_to_key
 
numbers = [30, 5, 12]
print(sorted(numbers, key=cmp_to_key(lambda a, b: (a > b) - (a < b))))

The output is:

[5, 12, 30]

The expression (a > b) - (a < b) gives -1 when a is smaller, 0 when they are equal and 1 when a is bigger. That is the answer the sort needs. The sorted function calls the comparison again and again, on pairs of items, until it can place every item.

For most sorts, a key function is simpler. sorted(students, key=lambda s: s.score) answers the question by comparing one value per item. Most of the bugs in this lesson come from writing the comparison by hand when a key would have been correct.

The four rules

A comparison has to behave like a real ordering. The sorting code assumes four properties. If one of them breaks, the sort can give a wrong answer.

1. Equal to itself. Comparing an item with itself gives zero. An item is never before itself.
2. Opposite answers. If compare(a, b) is negative, then compare(b, a) must be positive. If compare(a, b) is zero, then compare(b, a) must be zero too.
3. No cycles. If a comes before b, and b comes before c, then a must come before c. Think of rock, paper and scissors. Paper beats rock, scissors beats paper, rock beats scissors. You cannot line the three up in one order, and a sort cannot place them either.
4. Same answer every time. Asking the same question twice must give the same answer. The comparison must not depend on random numbers, on a clock, or on a value that changes during the sort.

Keep these four in mind as you read the bugs below. Each bug breaks at least one of them.

Bug 1: subtraction that overflows

In Java, many people write a - b to compare two numbers, and that can overflow. An int in Java holds only whole numbers from about -2.1 billion to 2.1 billion, and a result past either end wraps around to the other end of the range. Python does not have this problem, because its integers grow as large as they need to be.

The next program runs the subtraction comparison on a very large number and on a very negative one.

The output is:

big - (-1) = 9223372036854775808
with subtraction: [-1, 0, 9223372036854775807]
with a real compare: [-1, 0, 9223372036854775807]

The subtraction gives the exact answer, one more than the largest 64-bit number, and the list is sorted correctly. So in Python, a - b is a safe comparison for int values of any size.

Two cases still need care. Numbers from other libraries, such as fixed-size numbers from a database or from a compiled extension, can have a size limit, and subtraction can overflow there. The same comparison written in Java for int values is also unsafe. A comparison that uses < and > avoids the question entirely, so it is the form to prefer, and it is the same form that the Java lesson recommends.

Bug 2: a comparison that returns true or false

Some people reason that a comparison function should answer "is a bigger than b?", which is a yes or no question. Python accepts that, because True and False are numbers too: True is 1 and False is 0. But the sort never receives a negative number, so it never decides that an item comes first.

The next program sorts a list with a true-or-false comparison and with a 1-or-0 comparison.

The output is:

bool comparison: [3, 1, 4, 1, 5, 9, 2, 6]
1 or 0 comparison: [3, 1, 4, 1, 5, 9, 2, 6]

Both outputs are the input, unchanged. No error is raised. The comparison never returns a negative number, so the sort never decides that one item comes before another. This is the most dangerous kind of comparison bug, because nothing warns you. The fix is to return a negative number, as the first example in this lesson does with (x > y) - (x < y).

Bug 3: equal items reported as "less"

This is the bug the lesson is named for. Suppose a student sort uses this comparison:

key = cmp_to_key(lambda a, b: -1 if a.score <= b.score else 1)

The author meant this: "a comes first when its score is lower or equal." Look at what happens when two students have the same score. Calling compare(a, b) returns -1, which says a comes first. Calling compare(b, a) also returns -1, which says b comes first. Both cannot be true, so rule 2 is broken. Rule 1 is broken too, because comparing an item with itself returns -1 instead of zero.

Here is a complete program that uses this comparison on four students. Two of them have score 2. The input lists Asha before Meera, and both have score 2. The @dataclass line makes a class that only holds named fields, here name and score.

The output is:

['Dev', 'Ravi', 'Meera', 'Asha']
scores in order: True

The scores are in order, but Meera now comes before Asha, although Asha was first in the input. No error was raised, and a quick look at the scores would pass. The rule that broke is the one about equal items. Only a check on the order of equal items shows the bug.

This is the silent form of the bug. Java's sort checks some of its comparisons while it merges, and it can stop with an IllegalArgumentException that says the comparison violates its general contract. Python's sort does not make that check. A comparison that breaks the contract may give a plausible order for a long time, and then give a wrong one for other data. Do not rely on a bad comparison looking right on a small test.

The fix is the one from the sorting lessons: compare the scores with < and >, and let the sort keep equal items in their input order. The key lambda s: s.score does exactly that, because sorted is stable.

The output is:

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

Asha and Meera both have score 2, and they keep their input order, so Asha comes before Meera.

Bug 4: a comparison that is random or changes during the sort

Rule 4 says the answer must be the same every time. A comparison that uses random.random(), the current time, or a value that another thread updates while the sort runs breaks this rule. The sort asks about the same pair twice and gets two different answers, and the sort's assumptions fail.

The next program sorts 200 numbers with a comparison that returns a random value from -1 to 1 for each call. It counts how many pairs are out of order in the result.

The output is:

adjacent pairs out of order: 101
same values as the input: True

The values are all still there, but 101 of the 199 neighbouring pairs are out of order. No error was raised. The fix is to remove the randomness from the comparison. If you need a random order, shuffle the list first with random.shuffle, and then sort with a fixed key.

Bug 5: null values

A None is Python's way of saying "no value here". A field that holds None cannot be compared with a number, so the comparison fails when it reaches that item. Here is a sort where one student has no score.

The output is:

Traceback (most recent call last):
  File "none.py", line 9, in <module>
    print(sorted(students, key=lambda s: s.score))
          ~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: '<' not supported between instances of 'NoneType' and 'int'

The last line says the < comparison met a NoneType, which is the type of None, and an int. The fix is to say where the None values go. A key that is a tuple does this. Its first item is True for a missing score and False otherwise, and its second item is the score itself, or 0 when it is missing. Python compares the first items first, so the missing scores go to one end.

The output is:

nulls last: ['Ana', 'Cy', 'Ben']
nulls first: ['Ben', 'Ana', 'Cy']

The first line puts Ben, whose score is missing, at the end. The second line puts him at the start. The expression s.score or 0 gives the score when it exists and 0 when it is None, so the second item of the tuple is always a number. That is what keeps the comparison from meeting a None.

How to check a comparison before you trust it

You can test a comparison in a few minutes. The checker from the comparison contracts lesson in this module runs the four rules on a list of sample items, and returns a short message for the first broken rule. Use it on your comparison with these samples:

• Several items with the same key. Their answers must be zero against each other, or the sort must keep their input order.
• Items at the edges of the range, such as the largest and smallest numbers you expect.
• A None, if the field can be missing.
• A list of at least 30 items with many equal keys. A short list can hide a bug that a longer one shows.

Most of the time, a key function passes these checks by design. A key that returns one value per item, or a tuple of values, cannot break the rules, because the sort compares the values with < and >. Hand-written comparison functions are where the bugs come from.

Common mistakes

Here is a short list of the problems you will meet, with what each one means.

• A list that is simply in the wrong order, with no error, usually comes from a comparison that never returns a negative number, such as a true-or-false answer.
• A list where equal items come out in the wrong order, with no error, usually comes from a comparison that returns -1 for equal items.
• A list with some values in the wrong place, with no error, usually comes from a comparison that gives a different answer each time it is asked.
• TypeError: '<' not supported between instances of 'NoneType' and 'int' means a key was None. Put a tuple key in front of the value, with a True or False first item, as the null example shows.
• TypeError: bad operand type for unary -: 'str' means a minus sign was put on text. Use reverse=True on a separate sort, or sort the text first and the number last.
• Writing a comparison that returns a yes or no answer for a list of values. Return the sign with (a > b) - (a < b), or use a key.

Practice

Exercise 1. A list of people is sorted with key=cmp_to_key(lambda p, q: p.age - q.age). One person has an age of 2000000000 and another has an age of -2000000000. Which person comes first after the sort, and why?

Show the answer

In Python the subtraction is exact, so 2000000000 - (-2000000000) is 4000000000, which is positive. The comparison says the person aged 2000000000 comes after the other one, so the order is correct. The same subtraction in Java with int values wraps around and gives a negative number, which puts the wrong person first. The lesson's example shows the Python result. The form to prefer in both languages is a key, key=lambda p: p.age, which compares the numbers directly.

Exercise 2. Explain why lambda a, b: 1 if len(a) > len(b) else 0 does not sort strings by length.

Show the answer

The comparison never returns a negative number. The sort needs a negative answer to decide that a comes before b. With this comparison, a shorter string never comes before a longer one, so the order it produces is not the length order. No error is raised, which makes it a silent bug. The fix is key=len, which compares the lengths directly.

Exercise 3. Find the broken rule in this comparison, and say how you would test for it.

lambda a, b: -1 if a.score < b.score else 1

Show the answer

When two items have equal scores, the condition is false, so the comparison returns 1. Calling compare(a, b) gives 1, and calling compare(b, a) also gives 1. Rule 2 says those two answers must have opposite signs or both be zero. Rule 1 is also broken, because comparing an item with itself returns 1. To test it, compare one item with itself, and compare two items with the same score in both orders. Any answer other than zero for the first test, or the same sign in both orders for the second, shows the bug.

Exercise 4. Write a key for Student objects with name and score fields. Sort by score from highest to lowest. Students with the same score must be ordered by name from A to Z. Do not use a comparison function.

Show the answer

sorted(students, key=lambda s: (-s.score, s.name))

The minus sign on the score puts the higher scores first, and the name breaks ties in alphabetical order. The minus sign works here because the score is a number.

Exercise 5. A list of Student objects has some names that are None. Sort the list by name, with the None names at the end, and without an exception.

Show the answer

sorted(students, key=lambda s: (s.name is None, s.name or ""))

The first item of the tuple is True for a missing name, so those students sort after the others. The second item is the name itself, or an empty text when the name is None, so the comparison never meets a None.

Summary

• A comparison returns a negative number, zero or a positive number, and it must follow four rules: equal to itself, opposite answers, no cycles, and the same answer every time.
• A key function such as key=lambda s: s.score cannot break these rules, because the sort compares the values with < and >.
• A comparison that returns a yes or no answer, or never returns a negative number, leaves the list unsorted without any warning.
• Returning -1 for equal items breaks the rules, and Python gives no warning. Equal items can come out in the wrong order.
• A random comparison gives a wrong list with no error.
• None values need a tuple key, with a True or False first item, or the sort raises a TypeError.
• Python integers do not overflow, so subtraction is exact here. Use < and >, or a key, when the same code may move to a language with fixed-size numbers.