We're back after a server migration that caused effbot.org to fall over a bit harder than expected. Expect some glitches.

I want to do a complicated sort: can you do a Schwartzian Transform in Python?

The technique, attributed to Randal Schwartz of the Perl community, sorts the elements of a list by first prepending a “sort key” to each element, and then sorting everything using the default sort comparision method, at full speed.

In Python literature, this technique is often referred to as Decorate-Sort-Undecorate (DSU).

To implement DSU in Python 2.4 and newer, you can simply pass in a key transform to the sorted function or the sort method:

Usorted = sorted(L, key=lambda s: s.upper())

L.sort(key=lambda s: s.upper())

In earlier versions, you can use list comprehensions instead. To sort a list of strings by their uppercase values:

tmp1 = [ (x.upper(), x) for x in L ] # decorate
tmp1.sort()
Usorted = [ x[1] for x in tmp1 ] # undecorate

To sort by the integer value of a subfield extending from positions 10-15 in each string:

tmp2 = [ (int(s[10:15]), s) for s in L ] # decorate
tmp2.sort()
Isorted = [ x[1] for x in tmp2 ] # undecorate

Note that Isorted may also be computed by

def intfield(s):
    return int(s[10:15])

def Icmp(s1, s2):
    return cmp(intfield(s1), intfield(s2))

Isorted = L[:]
Isorted.sort(Icmp)

but since this method calls intfield() many times for each element of L, instead of just once per element, it can be a lot slower than the DSU approach.