@amphetamine That's what I ended up trying :( https://users.rust-lang.org/t/sort-with-indices/18720 Using this as a base
@eden Finding sort order is equivalent to sorting the array (if you have sort order getting sorted array is O(N), sorting has usually higher complexity).
Since they are equivalent there is not reason not to sort.
If you need to get sort order just create a list of tuples (1 1), (4, 2), (3, 3) (5, 4) and then sort them using first element, then you'll get sort order.
In numpy you have argsort method which is useful: https://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html .
@jacek ooh, I think I can use this. I thought they're not quite equivalent for some types of sort, because you'll move items in blocks rather then repositioning, but I didn't think about adding in an index.
So for my case, I think I can sort tuples in Rust and get the paired index, thanks!
@eden As you mentioned, any sorting algorithm can get you a permutation that sorts the list.
It turns out that it's (asymptotically) optimal, as you can apply the permutation in linear time and constant space, and you can't sort or find a sorting permutation in sublinear time (yes, autocarrot, sublinear is sublimer, but it's not what I meant) because you need to read the whole list.
Interestingly, the classical result about sorting using at least O(n log n) calls to the comparison function (assuming that is the only operation you have on elements) is most easily proved by looking for the sorting permutation:
Let's say you have n distinct items, there is exactly one sorting permutation, out of n! possible permutations.
Since the only way to get information about which permutation it is, is through the comparison function, and that it provides a single bit of information per call, you need at least log2(n!) / (1 bit / call) ~ n log n calls