Notation for argsort

Question

I writing up a paper and I need a clear description of numpy's argsort.

If we take set $X = \{x_1,\ldots,x_n\}$ could we describe argsort as $$ \underset{i}{\text{argsort}X} = |\{x_j \mid x_j \lt x_i, x_j \in X \}| $$ ?

Answer 1

Your description is not correct; for instance, if you take the argsort of $[9, 7, 8]$ you should get $[1, 2, 0]$ because the lowest term is at index $1$ in the list, the next is at index $2$ and the last is at index $0$. Your definition gives $[2, 0, 1]$ which represents that the term at the zeroth index ($9$) ends up at the second index when sorted - but that's not what Python's argsort returns. Formally, if you're thinking about permutations, your description returns the inverse permutation to the one returned by argsort.

It's better just to describe the post-condition, I think:

If L is a list, then argsort(L) is the lexicographically least permutation of the indices [0, ... , len(L) - 1] such that L[argsort(L)] is sorted.

This assumes your reader is happy with the Python convention of indexing one sequence by another - otherwise, you'd have to expand it as L[argsort(L)[0]], L[argsort(L)[1]], .... You might also take an alternate description which is somewhat more explicit as an instance of a typical sorting problem:

argsort(L) returns the list [0, ... , len(L) - 1] sorted by the order defined by i < j if L[i] < L[j] or L[i]=L[j] and i < j in the usual order of integers.

This sort of description is also plenty clear and might be more appreciated by anyone reading the paper who is not using numpy, since it's easy to tell a generic sorting algorithm to do this task if no argsort is provided in whatever environment the reader is working in.