@amphetamine So it seems to be roughly the same amount of work, but there's no Rust sort that gives that you info by default, even though it's used in the function.

@eden hnnnnmmmmm annoying

i could have sworn there was one

if you can use an iterator you can maybe work something out with enumerate()

@amphetamine That's what I ended up trying :( https://users.rust-lang.org/t/sort-with-indices/18720 Using this as a base

@eden

In MATLAB, the sort function can also return the indexes/mapping.

@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 you can just count the numbers that are bigger than the one you want to figure out the position of

@eden duplicates receive the same position in this case

@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

amphetamine tokyo@amphetamine@social.wxcafe.net@eden i think it's the same amount of work, like calling SELECT on every member of the list