Stability and sorted()

When records are sorted by one field, several records can have the same value in that field. A stable sort keeps those records in the order they came in. Python’s sort is stable, and that makes sorting by several fields simple.

What stable means

A sort is stable if any two records with equal keys come out in the same order as they went in. The key is the part used for comparing, such as the platform number of a train. Step through both sorts:

Insertion sort and merge sort are stable: they only move a record past records with a strictly larger key. Selection sort, quick sort and heap sort are not, because their long-distance swaps can jump a record over an equal one.

sorted() and list.sort()

sorted(a)                  # a new sorted list; a is unchanged
a.sort()                   # sorts a in place, returns None
sorted(a, reverse=True)    # largest first, still stable
sorted(trains, key=lambda t: t.platform)

Both use Timsort: a merge sort that first finds runs that are already in order, so it is O(n) on sorted or nearly sorted data and O(n log n) in the worst case. It is stable. It needs up to O(n) extra space.

key= takes a function. It is called once per item, and the items are sorted by what it returns. This is faster and simpler than writing a comparison function. a.sort() returns None, so a = a.sort() loses your list.

Sorting by several fields

Suppose trains must be ordered by platform, and trains on the same platform by departure time. Two ways:

# 1. One sort, with a tuple key: compares platform, then time
sorted(trains, key=lambda t: (t.platform, t.time))

# 2. Two stable sorts: the LAST sort is the main one
s = sorted(trains, key=lambda t: t.time)
s = sorted(s, key=lambda t: t.platform)

The second way works because of stability: the platform sort keeps the time order among trains on the same platform. It is useful when one field must go the other way. For numbers, negate the key: key=lambda t: (t.platform, -t.time). Strings cannot be negated; stability gives a way to do it then, which SORT-P6 asks you to find.

Useful patterns

• sorted(range(n), key=lambda i: a[i]) gives the positions in sorted order, called an argsort. Ties keep the smaller index first.
• operator.itemgetter(1) and operator.attrgetter("time") are fast ready-made key functions.
• min, max and heapq.nsmallest take key= too. If you only need the smallest few, do not sort everything (lesson 8).

Now try SORT-P6, The departure board.