Python: How to keep track of how a list was sorted?

Question

Given a list l0 of numbers in arbitrary order that may contain duplicates, how to have it sorted to l_s while keeping track of how l0 was sorted, so that the original l0_order can be reproduced later on (l_in_l0_order)?

The point is to apply l0_order to another list l that is in l_s order to retrieve a list l_in_l0_order ordered according to l0.

What I use so far is

l0 = [1, 7, 3, 12, 12, 4]
ls = sorted(l0)
# ls
# [1, 3, 4, 7, 12, 12]

l0_order = [ls.index(v) for v in l0]
l_in_l0_order = [ls[i] for i in l0_order]
# l_in_l0_order
# [1, 7, 3, 12, 12, 4]

is there a more clever way to do this? For large lists, this make a lot of calls to index

Note: for a list with elements with equal value but different id, the method above can produce invalid results because index (afaik) compares values, not ids. I do not require that behavior (order of id), but it might be of relevance for a general solution.

Is numpy not an option? You could just go with `argsort` if performance is an issue — yatu, Dec 19 '19 at 11:25
Downvoting is fine - but please leave a comment ***why*** to make room for improvement. Otherwise, this is just *not helpful*. Thank you. — FObersteiner, Jan 26 '21 at 11:10

Amadan · Accepted Answer · 2019-12-19T11:50:09.060

Your system will fail if you have items in l0 that are equal but not identical. Furthermore, the use of .index on every member is unnecessary bloat, O(N^2). In these kinds of circumstances, you want to sort the keys, and then look up the elements, rather than sort the elements and look up the keys as you did. For one thing, looking up elements by key is fast; for another, there is no ambiguity which element you're fetching.

order = sorted(list(range(len(l0))), key=lambda i: l0[i])
l1 = [l0[i] for i in order]

As said in comments, numpy.argsort does the same thing.

To reverse the permutation, you can repeat the same process on order:

inverse_order = sorted(order, key=lambda i: order[i])
l0_again = [l1[i] for i in inverse_order]

Obviously, you can use the same process to put another list that is in l1 order back into l0 order:

ls_in_l0_order = [ls[i] for i in inverse_order]

Python: How to keep track of how a list was sorted?

1 Answers1