# Use of `Perm` to find sorted subset of indices?

I want to use `sortperm` on only a subset of indices of an array `a`, I couldn’t find how to do it with the sortperm function, I can simply use `sort` on the subset of indices `s_subs` this way:
`sort(s_subs, by = x -> a[x])`
It seems however that using a function that refers to an external array (here `a`) seems to be quite slow.

By looking a bit in the code of the sorting functions in Base, I understood that the non-exported `Perm` ordering possibly does what I want faster:
`sort(s_subs, order = Perm(Forward, a))`

Since `Perm` is not exported, I am cautious about its use. Are there any caveats about using it this way (I already noticed that bounds aren’t checked), or is there a better way to do what I want?

Thanks!

1 Like

I may have misunderstood, but would `sortperm(a[s_subs])` work for you?

This gives indices ranging from 1 to `length(s_subs)`, while I want the indices in `s_subs` to be sorted, `s_subs` can be any subset of indices ranging from 1 to `length(a)`.

I see. What about `s_subs[sortperm(a[s_subs])]`?

Hopefully someone else chimes in with a cleaner and faster solution.

1 Like

@Adriel, your solution looks good but it seems slower than the two OP solutions, of which the first one seems faster for integer arrays and the second for float arrays.

EDIT:
For some large number of subindices and/or large vectors, your function actually seems to be faster. For example:

``````n = 100_000
a = rand(n)
s_subs = rand(1:n, 5_000)
``````
3 Likes

Could that be because @Adriel’s solution does the sorting by operating on a smaller array (the copy `a[s_subs]`) and not the whole array `a` directly?

I am referring to this:
Recently stumbled upon `partialsortperm`. Is this what you are looking for?
I think that `partialsortperm` takes a range containing the “order” and gives the indices corresponding to that order.
From the example of the documentation: `partialsortperm(v, 1:3)` would give the indices of the 3 smallest elements of `v`. I somehow want the opposite, I want to give the indices and have them returned in order.