Python's sort: keys and stability

In your programs, sort with Python's own tools. sorted(values) returns a new sorted list and leaves values as it was. values.sort() sorts the list itself and returns None. Mixing them up is a classic bug:

names = ["Mia", "Ann", "Zoe"]
names = names.sort()
print(names[0])

Traceback (most recent call last):
  File "main.py", line 3, in <module>
    print(names[0])
          ~~~~~^^^
TypeError: 'NoneType' object is not subscriptable

names.sort() sorted the list and returned None, and the assignment put that None in names. Write names.sort() on its own line, or names = sorted(names).

What Python's sort costs

Both use Timsort, an algorithm written in C for Python. It's a merge sort that first finds runs of items that are already in order and then merges the runs. So:

• it's O(n log n), in the worst case too;
• it's O(n) on a list that is already sorted, and fast on nearly sorted lists, like insertion sort;
• it's stable: items that compare equal keep their order;
• sorted makes a new list, O(n) memory.

Running in C, it's many times faster than a comparison sort written in Python, such as your own merge sort. That merge sort teaches how sorting works; in a program, use sorted. (Counting sort on small whole numbers, from the step before, is the exception that can beat it.)

Keys, briefly

key= gives a function that returns what to sort each item by. Python calls it once for each item, n calls in all, not once for every comparison. A tuple as the key sorts by its first item, and by the second where the first ones are equal: key=lambda p: (-p.points, p.name) puts the most points first and equal points by name. For strings, remember that capital letters come before small ones ("Zoe" < "ann" is True); key=str.lower compares them as small letters.

Stability and sorting in several passes

A minus sign turns a number's order around, but you can't put a minus sign in front of a string. Say players should be listed by team from Z to A, and by name from A to Z in each team. Stability gives a way: sort several times, the least important order first. Each later sort keeps the order of the items it finds equal:

players = [("Ann", "Owls"), ("Bob", "Bees"), ("Cid", "Owls"), ("Ada", "Bees"), ("Eve", "Owls")]
players.sort(key=lambda player: player[0])
players.sort(key=lambda player: player[1], reverse=True)
for name, team in players:
    print(team, name)

Owls Ann
Owls Cid
Owls Eve
Bees Ada
Bees Bob

The first sort puts the names in order. The second sorts by team, from Z to A, and keeps the players of each team in the order the first sort left them. reverse=True is stable too: equal items keep their order, they aren't reversed. That's not the same as sorting and then reversing the whole list, which reverses equal items too. Two sorts cost O(n log n) each, so still O(n log n) in all.

Sorting objects

You've sorted objects with a key that reads an attribute. A class can also define < itself, with the method __lt__: sorting compares items only with <, so then sorted works without a key. Version numbers are a good example, because as strings they sort wrongly ("1.10.0" comes before "1.2.5"):

class Version:
    def __init__(self, text):
        self.text = text
        self.parts = tuple(int(part) for part in text.split("."))

    def __lt__(self, other):
        return self.parts < other.parts


texts = ["1.10.0", "1.2.5", "1.2.10", "0.9"]
print(sorted(texts))
print([version.text for version in sorted(Version(text) for text in texts)])

['0.9', '1.10.0', '1.2.10', '1.2.5']
['0.9', '1.2.5', '1.2.10', '1.10.0']

The tuples (1, 2, 10) and (1, 10, 0) compare number by number, so 2 comes before 10, as it should.

Sort first, then look at neighbors

Sorting is often the first step of a faster algorithm. After sorting, items that are close sit side by side, so questions about pairs (repeats, the closest two, overlapping times) need only a look at each item's neighbor. Say you want the two prices that are closest to each other. Instead of comparing every pair, sort the prices and compare each one with the one just before it:

prices = [42, 17, 93, 58, 25, 61]
ordered = sorted(prices)
pair = (ordered[0], ordered[1])
for i in range(2, len(ordered)):
    if ordered[i] - ordered[i - 1] < pair[1] - pair[0]:
        pair = (ordered[i - 1], ordered[i])
print(ordered)
print(pair)

[17, 25, 42, 58, 61, 93]
(58, 61)

Why are neighbors enough? Take two prices a and c that aren't side by side in the sorted list. The price right after a, call it b, sits between them: a <= b <= c, so b - a is at most c - a. The neighbors a and b are at least as close, so a pair that is further apart in the sorted order never beats the best pair of neighbors. Repeats work the same way: equal values end up side by side. The cost is O(n log n) for the sort and O(n) for the pass, instead of O(n²) for all the pairs.

Meetings: fit the most

Another interview classic starts with a sort. It's about intervals, pairs (start, end) such as meetings, where a meeting that ends at 60 doesn't clash with one that starts at 60. To fit the most meetings into one room, sort them by their end, and take each meeting that starts once the last one taken has ended:

def most_meetings(meetings):
    chosen = []
    for start, end in sorted(meetings, key=lambda meeting: meeting[1]):
        if not chosen or start >= chosen[-1][1]:
            chosen.append((start, end))
    return chosen


meetings = [(60, 90), (0, 30), (25, 50), (10, 20), (100, 130), (85, 110)]
print(most_meetings(meetings))

[(10, 20), (25, 50), (60, 90), (100, 130)]

That's O(n log n) for the sort and O(n) for the pass. most_meetings makes a greedy choice: it takes what looks best right now, the meeting that ends first, and never goes back on it. Greedy choices can go wrong (the module on dynamic programming shows some), but this one is safe. Take any plan with the most meetings. Its first meeting ends no earlier than the meeting that ends first of all, so swapping the two leaves room for every other meeting in the plan. So some best plan starts with the meeting that ends first, and the same argument works for each meeting after it. Sorted by start instead, (0, 30) would be taken first, and it leaves room for only 3 meetings.