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

**URL:** <https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912>\
**Category:** General Usage\
**Tags:** sort, sortperm\
**Created:** [November 3, 2021, 8:53pm UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912 "2021-11-03T20:53:25Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![mehdi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mehdi/32/28394_2.png) [@mehdi](https://discourse.julialang.org/u/mehdi)\
**Post date:** [November 3, 2021, 8:53pm UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/1 "2021-11-03T20:53:25Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![Adriel](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Adriel](https://discourse.julialang.org/u/Adriel)\
**Post date:** [November 4, 2021, 3:16am UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/2 "2021-11-04T03:16:57Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mehdi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mehdi/32/28394_2.png) [@mehdi](https://discourse.julialang.org/u/mehdi)\
**Post date:** [November 4, 2021, 3:26am UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/3 "2021-11-04T03:26:41Z")

</div>

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)`.

---

<div class="post-metadata">

**Author:** ![Adriel](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@Adriel](https://discourse.julialang.org/u/Adriel)\
**Post date:** [November 4, 2021, 3:55am UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/4 "2021-11-04T03:55:51Z")

</div>

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

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

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [November 4, 2021, 7:37am UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/5 "2021-11-04T07:37:16Z")

</div>

@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:_

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

```

---

<div class="post-metadata">

**Author:** ![mehdi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mehdi/32/28394_2.png) [@mehdi](https://discourse.julialang.org/u/mehdi)\
**Post date:** [November 5, 2021, 6:55pm UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/6 "2021-11-05T18:55:33Z")

</div>

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:  
[https://docs.julialang.org/en/v1/manual/performance-tips/#Copying-data-is-not-always-bad](https://docs.julialang.org/en/v1/manual/performance-tips/#Copying-data-is-not-always-bad)

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 5, 2021, 6:59pm UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/7 "2021-11-05T18:59:08Z")

</div>

Recently stumbled upon [`partialsortperm`](https://docs.julialang.org/en/v1/base/sort/#Base.Sort.partialsortperm). Is this what you are looking for?

---

<div class="post-metadata">

**Author:** ![mehdi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mehdi/32/28394_2.png) [@mehdi](https://discourse.julialang.org/u/mehdi)\
**Post date:** [November 5, 2021, 7:07pm UTC](https://discourse.julialang.org/t/use-of-perm-to-find-sorted-subset-of-indices/70912/8 "2021-11-05T19:07:00Z")

</div>

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.