Lexicographic comparison in Python

Why it matters

Sorting is one of the first things a program does with text. A contact list is sorted by name, a dictionary by word and a file listing by file name. Each of these needs a rule that says which of two strings comes first. The rule most programs use is called lexicographic order. It is the order of a dictionary, extended to every character a computer can store.

Beginners are often surprised by this order. The word Zebra comes before apple. The number text 10 comes before 9. A capital B comes before a lowercase a. None of these is a bug. Each follows from one simple rule, and once you know the rule you can predict the result of any comparison before you run the code.

This lesson covers how the comparison works, how the operators < and > and the function sorted use it, and how to sort without caring about case. Sorting numbers, custom objects and multiple keys is covered in the sorting modules. This lesson stays with text.

The idea: compare the characters in order

Every character has a number. Computers store characters as numbers, and the most common table for English letters and digits is ASCII. In that table the digit 0 is 48, the uppercase A is 65, the uppercase B is 66, the lowercase a is 97 and the lowercase b is 98. You can check these in Python with ord, which returns the number of a character.

A lexicographic comparison walks two strings from the left, one character at a time. It stops at the first position where the characters differ and says which string has the smaller number there. If one string is a prefix of the other, which means it matches the other string from the start and then ends, the shorter string comes first.

Think of a dictionary. car comes before cat because the first two letters match and then r comes before t. car comes before cart because car ends first. Python does the same thing with the character numbers.

In Python, < on two strings returns True or False. The rule is the same one a dictionary uses. Python does not return a number like the -1, 0 and 1 that some other languages give. If you need a three-way result, build it from two comparisons, as the next section shows.

Worked example 1: the comparison operators and the three-way result

The first program compares pairs of strings and prints the answer. Predict each answer before you run the code, then check your prediction against the output.

The output is:

True False
True
True False
True False
True True False
False

The first line compares apple with banana. The first characters are a (97) and b (98). The first is smaller, so apple < banana is True. The second part of the line is False, because banana is not smaller than apple.

The line "B" < "a" is True. The character B is 66 and a is 97, so B comes first. Every uppercase letter has a smaller number than every lowercase letter in ASCII. That is why Zebra comes before apple, and why Apple comes before apple.

The line "10" < "9" is True. The first characters are 1 (49) and 9 (57). The comparison stops at the first character, so 10 sorts before 9. This is the reason a list of numbers stored as text comes out in the wrong order, as the mistakes section shows.

The lines "apple" < "apples" and "apples" < "apple" show the prefix rule. The shorter string comes first, so the first result is True and the second is False.

Some code needs a three-way answer: negative when the first string comes first, zero when they are equal, and positive when it comes later. Python does not have a built-in function for that, but two comparisons give the same answer as a number:

The output is:

-1 1 0
-1 1

The expression (a > b) - (a < b) works because True counts as 1 and False counts as 0 in arithmetic. The result has a clear sign, and you should test the sign, not an exact size. The version of compare in this lesson always returns -1, 0 or 1, but other ways of building a comparison may return different sizes, so the sign is the part to depend on.

The last part of the output shows the character numbers behind these results. ord("B") - ord("a") is -31, and that size is a detail of the numbers, not a rule for your code.

Worked example 2: sorting words, with and without case

The function sorted returns a new list in lexicographic order. It uses the same comparison as the operators. The list below is sorted in three ways. Read each result, and explain why the first list puts the digits and the uppercase words first.

The output is:

['10', '9', 'Apple', 'Banana', 'apple', 'banana', 'cherry']
['10', '9', 'Apple', 'apple', 'banana', 'Banana', 'cherry']
['10', '100', '25', '9']
['9', '10', '25', '100']

The first line sorts the words by their character numbers. The digits come first because 1 and 9 are below the letters, and Apple and Banana come before the lowercase words, because uppercase letters have smaller numbers.

The second line uses the argument key=str.lower. The key argument gives the value to compare for each item, so every word is compared by its lowercase form. The words are still returned in their original form, and Apple and apple both appear, because they are different strings. Python's sort is stable, which means items with equal keys keep the order they had in the input. The input had Apple before apple, and banana before Banana, so the output keeps those pairs in the same order.

The third line is the trap. The strings 10, 9, 100 and 25 sort by their first characters, so 10 and 100 come before 25, and 9 comes last. The fourth line passes key=int, which compares the numbers the text stands for, and the result is 9, 10, 25, 100. The fix is to compare the number, not the text.

The reverse=True argument turns the order around. The call sorted(["delta", "Alpha", "charlie", "Bravo"], key=str.lower, reverse=True) gives delta, charlie, Bravo, Alpha, which is alphabetical from the end.

Worked example 3: a case-insensitive order with a tie rule

Sorting by a single rule is not always enough. Two names that differ only in case have the same key when the key is the lowercase form, so the order of the pair depends on the input. A second part of the key settles the tie. The program below sorts names ignoring case, and it breaks ties with the normal order, so the result does not depend on the input order.

The key is a tuple, which is a fixed group of values, and lambda s: ... is a one-line function with no name that builds it from s. Python compares tuples item by item, so the second item of the tuple is used only when the first items are equal.

The output is:

['Alice', 'alice', 'Bob', 'bob', 'carol']
['alice', 'Alice', 'bob', 'Bob', 'carol']
['Alice', 'alice', 'Bob', 'bob', 'Carol']

The first line uses the tuple key. The lowercase form decides the main order, so alice and Alice come before bob and Bob. For the pair Alice and alice, the lowercase forms are equal, so the second item decides. The plain string Alice compares before alice, because A has a smaller number than a. The same is true for Bob and bob.

The second line uses only the lowercase key. It keeps the input order for ties, so alice comes before Alice only because it was first in the input. If the input order changed, the output would change too. The first line does not depend on the input order, so use the tuple key when the output must be the same every time.

Accented letters need care. Python compares the code numbers of accented letters, and those numbers are above the ASCII letters, so the result can look wrong to a reader:

The output is:

['Zed', 'apple', 'eclair', 'resume', 'résumé', 'Éclair']
['apple', 'eclair', 'resume', 'résumé', 'Zed', 'Éclair']

The first line puts Éclair last, because É has a code above the ASCII letters. The rule is followed, but a reader expects Éclair next to eclair. The method str.casefold is a stronger form of lower. It is designed for case-insensitive matching, and it changes some letters in ways lower does not. The second line still puts Éclair last, because the sort compares the casefolded text, and é is a different letter from e.

Python's standard library does not have a sort that knows the accent rules of every language. For names and labels shown to people, use a library or the locale rules of the language you need. For internal keys, a plain order with a tie rule is usually enough, and the key must stay the same every time the program runs.

Worked example 4: the comparison also decides what counts as equal

A sorted collection of unique items keeps its items in order, and it decides whether a new item is already present by comparing it with the stored items. Python's set, which keeps each item once and has no order, does not sort, and it compares strings exactly, so a case-insensitive rule needs a dictionary keyed by the lowercase form. The next program keeps the first item that has each key.

The output is:

['10', '9', 'Apple', 'Pear', 'apple', 'pear']
['pear', 'Apple', '10', '9']
True False

The plain set keeps all six strings as sorted unique strings, because each one differs from the others by its characters. The case-insensitive dictionary keeps only four. The second apple was refused because Apple already had the key apple, and the second Pear was refused because pear already had the key pear. The method setdefault stores a value only when the key is missing, so the item kept is the first one added. The lookup for PEAR finds pear through its lowercase key, and it finds nothing in the plain set.

This matters when you choose a rule for equality. A case-insensitive rule is right for a list of usernames that must be unique regardless of case. It is wrong for a list of passwords, where Pear and pear are different values.

Common mistakes

Mistake 1: comparing a string with a number. Python does not guess what you mean when you compare text with a number. The comparison raises an error:

The output is:

TypeError: '<' not supported between instances of 'str' and 'int'

The fix is to convert one side with int() or str(), so both sides have the same type. The same error appears when one side is None:

The output is:

TypeError: '<' not supported between instances of 'str' and 'NoneType'

Check for None first, as in if value is not None and value < "m":.

Mistake 2: expecting digits to sort as numbers. The result ['10', '9', 'Apple', ...] in worked example 2 is correct for text. A list of strings that hold numbers sorts character by character, so 10 comes before 9. Convert to a number first, with key=int, or keep the numbers as integers from the start.

Mistake 3: using is to compare strings. The is operator asks whether two names point to the same object, which is a different question from whether the characters match. Use == for text, as the first lesson explained. Use is only for None.

Mistake 4: a case-insensitive sort that ignores ties. If two names differ only in case, a key that uses only the lowercase form treats them as equal. The order of the pair then depends on the input and not on a rule. Add a second part to the key, as worked example 3 does, when the output must be the same every time.

Mistake 5: using lower for every case-insensitive check. For plain English, lower and casefold agree. For some letters from other alphabets, they do not, and casefold is the safer choice for comparing text that a user typed. The German letter ß shows the difference: "ß".casefold() is "ss", and "Straße".casefold() == "STRASSE".casefold() is True.

Mistake 6: comparing text with a number that looks the same. "9" == 9 is False, and "9" < 10 raises the error shown above. The text and the number are different types, even when they look alike on screen.

Practice

Try each exercise before you open its answer. Each answer shows the expected result.

1. Without running the code, decide whether "Zebra" < "apple" is True or False. Explain your answer in terms of character numbers.

Show the answer

It is True. The first characters are Z, which is 90, and a, which is 97. Ninety is less than 97, so Z comes first. The uppercase letters come before every lowercase letter in ASCII.

2. Sort the list ["Bob", "alice", "Carol", "bob", "Alice"] ignoring case. When two names differ only in case, put the one that compares first in the normal order first. Write the Python code and state the result.

Show the answer

Use the key from worked example 3:

names = ["Bob", "alice", "Carol", "bob", "Alice"]
print(sorted(names, key=lambda s: (s.lower(), s)))

The result is ['Alice', 'alice', 'Bob', 'bob', 'Carol']. The lowercase keys sort the names into alice, bob, carol. The second part of the key puts the uppercase Alice before alice and Bob before bob, because the uppercase letter has the smaller number.

3. A list holds the strings "100", "25" and "9". Sorting them with sorted gives ['100', '25', '9']. Explain why, then write one line that sorts them as numbers.

Show the answer

The first characters are 1, 2 and 9, and the comparison looks only at the first character until it finds a difference. The digit 1 is 49, 2 is 50 and 9 is 57, so 100 and 25 come before 9. Sort by the number instead:

print(sorted(["100", "25", "9"], key=int))

The result is ['9', '25', '100']. This is the same fix as the key=int line in worked example 2.

4. Write a function same_ignoring_case(a, b) that returns True when the two strings are equal ignoring letter case. Test it on "Hello" and "hELLO", and on "Hello" and "Hellos".

Show the answer

def same_ignoring_case(a, b):
    return a.casefold() == b.casefold()
 
print(same_ignoring_case("Hello", "hELLO"), same_ignoring_case("Hello", "Hellos"))

The output is True False. The function compares the casefolded forms with ==, so the test is on the text, not on the object.

5. What does print(sorted(["b", "A", "a", "B"])) print? Predict it from the character numbers before you run the code.

Show the answer

It prints ['A', 'B', 'a', 'b']. The uppercase letters A (65) and B (66) come before the lowercase letters a (97) and b (98). Within each group the letters are in alphabetical order.

Summary

• A lexicographic comparison walks two strings one character at a time and decides by the first character that differs, or by length when one string is a prefix of the other.
• Each character has a number. In ASCII, 0 is 48, A is 65, a is 97, and every uppercase letter comes before every lowercase letter.
• < and > return True or False. Use (a > b) - (a < b) when you need -1, 0 or 1, and test the sign, not the size.
• Sort numbers stored as text with key=int, or the order will be 10, 9.
• To ignore case, use a key with casefold(). Add a second part to the key for ties when the order must be the same every time.
• Do not compare a string with a number or with None. Python raises a TypeError.