sortandperm

[xiaodaigh]

I find that often times I would like to sort a vector and return its sortperm and I imagine having a function that returns both the sorted vector and its order is useful for say sorting DataFrames and many other applications.

Hence I propose to implement a function called sortandperm(v) which returns (sort(v), sortperm(v)) but uses a more optimized algorithm then the naive implementation

This should alleviate the slowness of #939 as well in some use cases.

[nalimilan]

Do you have evidence that it can be significantly faster to do both operations at the same time than calling perm = sortperm(x) and then x[perm]? Any examples in other languages maybe?

[xiaodaigh]

@nalimilan The source of sortperm actually calls sort!. This makes sense, to get permutation you need to sort the original vector. Hence it's possible to output both the sorted array and the permutation in the same run.

Demonstrably, sortperm in RadixSort can be made faster and a "byproduct" of the sortperm is the original vector sorted, hence it's better to just output the vector instead of x[perm] which is another step of computation that's already been performed in the sort. So I only have "evidence" from one implementation.

[StefanKarpinski]

Seems like a good feature. It would be good to really max the performance of sortperm out and then see what the performance difference ends up being. Intuitively computing them together does seem like it could be cheaper, but sometimes these things aren't that intuitive.

[xiaodaigh]

@nalimilan In regards to if this was done in other languages. I just looked at the latest documentation for sort in R and I found that it documented a parameter index.return. At least in R, this is done. See below direct-quote from the ?sort doc

index.return
logical indicating if the ordering index vector should be returned as well. Supported by method == "radix" for any na.last mode and data type, and the other methods when na.last = NA (the default) and fully sorting non-factors.