implement sortperm

[tpapp]

The package has a nice implementation of bitonic sort now thanks to @stev47 excellent #754, but lacks sortperm.

Stephan, do you think it would be possible to leverage existing code to add it, or would it require a substantial redesign?

[c42f]

I guess something like the following would be the low-effort implementation:

Base.sortperm(v::StaticVector) = first.(sort(tuple.(v,SVector{length(v)}(1:length(v)))))

Thence

julia> v = rand(SVector{6,Int})
6-element SArray{Tuple{6},Int64,1,6} with indices SOneTo(6):
 -1865929207925180621
 -5812688148380581253
  6391514714332745410
  1669729801171779512
 -9221712231859343250
 -6384757348221293365

julia> @btime sortperm($(Ref(v))[])
  8.458 ns (0 allocations: 0 bytes)
6-element SArray{Tuple{6},Int64,1,6} with indices SOneTo(6):
 5
 6
 2
 1
 4
 3

julia> @btime sortperm($(Ref(Vector(v)))[])
  135.444 ns (2 allocations: 144 bytes)
6-element Array{Int64,1}:
 5
 6
 2
 1
 4
 3

[c42f]

Or perhaps conceptually better (though slightly slower?)

julia> sortperm2(v) = sort(SVector{length(v)}(1:length(v)), by=i->v[i])

julia> @btime sortperm2($(Ref(v))[])
  11.084 ns (0 allocations: 0 bytes)

[stev47]

I tried something too, will open a pull request shortly.
It is twice as slow as @c42f implementation, but keeps the semantics of sortperm being stable. If you don't care about that, you can redefine Base.Order.lt(::Perm{<:Any,<:StaticVector}, a, b) to get the same performance.

[c42f]

Actually I think the first version I posted happens to be a stable sort? (Though by happy accident of tuples comparing lexicographically, not by any special foresight on my part!)

Base.sortperm(v::StaticVector) = first.(sort(tuple.(v,SVector{length(v)}(1:length(v)))))

This was also the faster version out of the two I posted - is there a simple way we can get performance like this but support all the standard fancy features like your PR?

By the way I don't think a third party package overloading Base.Order.lt(::Perm{<:Any,<:StaticVector}, a, b) is a practical option because it treats sort stability for StaticVector as a global setting. (More or less equivalently, one might complain that it's type piracy :-) )

[stev47]

You are right, I didn't catch that! I've commented over at #773