this problem occurs quite common in real applications: given a list of data, sort them with a key tuple (key_1, key_2, ..., key_n) where some but not all of them are reversed;

for example, we may have a list of site configs; each site config has a url, a user and a quota:

items = [
{
'url': 'http://aaa/',
'user': 'xxx',
'quota': 100,
},
{
'url': 'http://aaa/',
'user': 'yyy',
'quota': 200,
},
{
'url': 'http://bbb/',
'user': 'xxx',
'quota': 100,
},
{
'url': 'http://bbb/',
'user': 'yyy',
'quota': 200,
},
]


if we want to sort by (url, quota) in asc order, we can write:

from operator import itemgetter
ans = sorted(items, key=itemgetter('url', 'quota'), reverse=False)


if we want to sort by (url, quota) in desc order, we can write:

ans = sorted(items, key=itemgetter('url', 'quota'), reverse=True)


but what if we want to sort by (url, quota), with url in asc order but quota in desc order? the reverse parameter no longer works here;

clever people will notice quota is a number, so we can write:

ans = sorted(items, key=lambda x: (x['url'], -x['quota']), reverse=False)


but what if we want to sort by (url, user), with url in asc order but user in desc order? this time user is not a number so the minus sign wont work any more;

## solution

the general solution is to write an advanced sorted function, which takes in a richer format of keys:

def my_sorted(items, keys):

class _inv:
def __init__(self, val):
self.val = val
def __eq__(self, other):
return other.val == self.val
def __lt__(self, other):
return other.val < self.val

def _key(item):
ans = []
for key, reverse in keys:
val = key(item)
ans.append(_inv(val) if reverse else val)
return ans

return sorted(items, key=_key)


with this advanced function, we can write:

ans = my_sorted(items, keys=[
(itemgetter('url'), False),
(itemgetter('user'), True),
])


output:

[
{
"url": "http://aaa/",
"user": "yyy",
"quota": 200
},
{
"url": "http://aaa/",
"user": "xxx",
"quota": 100
},
{
"url": "http://bbb/",
"user": "yyy",
"quota": 200
},
{
"url": "http://bbb/",
"user": "xxx",
"quota": 100
}
]


this approach is general enough in that it works with all data types supporting __eq__ and __lt__ (except for the _inv class itself);

we can make the above approach even more general by organizing everything inside a key adapter so that it not only works with sorted but also with list.sort or anywhere a key is needed:

keys = [
(itemgetter('url'), False),
(itemgetter('user'), True),
]

class _:
def __init__(self, v): self.v = v
def __eq__(self, o): return o.v == self.v
def __lt__(self, o): return o.v < self.v
return lambda x: [ _(k(x)) if r else k(x) for k, r in keys ]



the adapter fits nicely into the current sort interface where a key is expected; you are using the same sort function so that client code needs minimal change;

## multi-pass sort

the approaches above perform single-pass sort by generating a tuple key from a key tuple; there is another multi-pass approach to solve the same problem; the key insight is that sorts are guaranteed to be stable in python3 (at least >= python3.5 per doc); so a sort on multiple columns can be broken into a series of sorts on each column in reverse column order:

for k, r in reversed(keys):
items.sort(key=k, reverse=r)


remember: for this approach to work, sort must be stable; this is true for builtin sort algos, but be careful if you use sort algos from other sources;

## performance

in general, single-pass sort and multi-pass sort have the same worst-case time complexity; assuming there are n items and each has dimension m, then both have worst-case time complexity O(m * n * log n); which is faster depends on the input; on different inputs, one can be 80%-100% faster than the other: https://bugs.python.org/file47877/performance-1.py

however, in the above single-pass sort impl, there is a performance hit with function adapter due to the large amount of wrapper objects; this is really a python artifact than a algo defect; the algo merely needs a piece of small info about which columns should be sorted in reverse order; using wrapper objects makes the code neat but creating a large amount of objects can be a performance overkill;

there is another single-pass sort algo proposed here; it wraps whole tuples instead of scalars in the tuple; a performance evaluation is here: https://bugs.python.org/file47880/performance-2.py

## conclusion

• the single-pass sort algo using adapter pattern introduced here features a simple calling interface supporting both scalar and vector keys; it adapts the key instead of introducing another sort function, which improves code readability and minimizes code change when the requirement varies; but be aware that performance may degrade (due to wrapper objects) as data scales;

• the multi-pass sort algo may run faster when you have a large amount of data (not guaranteed, as it is input-dependent); but you need to make sure the underlying sort algo is stable and passes go in reverse column order; you may write it as another function (such as my_sort) and call it instead of builtin sort; but this can make code unnecessary complicated;