Retrieving the permutation used to (un)sort a list

In this protip I provide a trick to sort a list and simultaneously compute the permutation mapping the position of an element in the sorted list to its position in the original list.

Here's the trick in Python, although the idea can be implemented in your language of choice:

>>> l = [ random.randint(1,1000) for _ in xrange(5) ]; l
[591, 760, 940, 764, 391]
>>> L = [ (l[i],i) for i in xrange(len(l)) ]
>>> L.sort()
>>> sorted_l,permutation = zip(*L)
>>> sorted_l
(391, 591, 760, 764, 940)
>>> permutation
(4, 0, 1, 3, 2)

This is typically useful when additional information related to the key is accessed via the index of the key in the original list.

Enjoy!