Sorting

Contents

Sorting#

Python’s sort and sorted use Timsort (adaptive merge sort, O(n log n) worst case, O(n) on already-sorted data, stable).

xs = [5, 1, 4, 2, 3]
xs.sort()                              # in place, returns None
ys = sorted(xs, reverse=True)          # new list

# custom key
people.sort(key=lambda p: p.age)
people.sort(key=lambda p: (p.last, p.first))   # stable multi-key

# operator.itemgetter / attrgetter are faster than lambdas
from operator import itemgetter, attrgetter
rows.sort(key=itemgetter(2))
people.sort(key=attrgetter("age"))

# decorate-sort-undecorate (DSU) when key computation is expensive
keyed = [(expensive(x), x) for x in xs]
keyed.sort()
xs_sorted = [x for _, x in keyed]

Stability matters when multi-key sorting by chained sorts: sort by the secondary key first, then the primary.

rows.sort(key=itemgetter(2))   # secondary
rows.sort(key=itemgetter(0))   # primary; secondary order preserved

References#

Contents