# How to sort a list of tuples according to another list

Posted on

### Question :

How to sort a list of tuples according to another list

There is a list:

``````a = [("ax", 1), ("ec", 3), ("bk", 5)]
``````

another list:

``````b = ["ec", "ax", "bk"]
``````

I want to sort `a` according to `b`:

``````sort_it(a, b)

a = [("ec", 3), ("ax", 1), ("bk", 5)]
``````

How to do this?

``````a.sort(key=lambda x: b.index(x))
``````

This sorts `a` in-place using the the index in `b` of the first element of each tuple from `a` as the values it sorts on.

Another, possibly cleaner, way of writing it would be:

``````a.sort(key=lambda (x,y): b.index(x))
``````

If you had large numbers of items, it might be more efficient to do things a bit differently, because `.index()` can be an expensive operation on a long list, and you don’t actually need to do a full sorting since you already know the order:

``````mapping = dict(a)
a[:] = [(x,mapping[x]) for x in b]
``````

Note that this will only work for a list of 2-tuples. If you want it to work for arbitrary-length tuples, you’d need to modify it slightly:

``````mapping = dict((x, x[1:]) for x in a)
a[:] = [(x,) + mapping[x] for x in b]
``````

Another posibility is to sort `a`, sort the indices of `b` according to `b` and than sort the `a` according to the indices

``````a.sort(key=lambda x: x)
ind = [i for i in sorted(enumerate(b),key=lambda x: x)]
a = [i for i in sorted(zip(a,ind),key=lambda x: x)]
``````

since every sorting takes n*log(n) this is still scalable for bigger lists

There’s actually a way to do this in linear O(n) time, because this isn’t really a sorting operation. The existence of the list `b` means that the sorting is already done; all we really need to do is to rearrange the elements of `a` to be in the same order. This can be done efficiently thanks to dictionaries.

``````from collections import defaultdict

def sorted_by(seq_to_sort, desired_order, key=None):
if key is None:
key = lambda x: x

# group the elements by their key
grouped_items = defaultdict(list)
for item in seq_to_sort:
k = key(item)
grouped_items[k].append(item)

# flatten the dict of groups to a list
return [item for key in desired_order for item in grouped_items[key]]
``````

Usage:

``````a = [("ax", 1), ("ec", 3), ("bk", 5)]
b = ["ec", "ax", "bk"]
result = sorted_by(a, b, lambda tup: tup)
print(result)  # output: [("ec", 3), ("ax", 1), ("bk", 5)]
``````

Notes:

• This is a stable sort; if two list items have the same key, their order will be preserved. Example:

``````>>> sorted_by([1, 2, 3], , key=lambda x: 5)
[1, 2, 3]
``````
• If any list elements are mapped to keys that don’t exist in `desired_order`, those elements are silently discarded. For example:

``````>>> sorted_by([1, 2, 3], [1, 2, 3], key=lambda x: 5)
[]
``````

``````[tup for lbl in b for tup in a if tup == lbl]