On the sorting algorithm

[putianyi889]

Benchmarking 5 different methods:

using TupleTools, Plots, StaticArrays, SortingNetworks
times1 = zeros(25)
times2 = zeros(25)
times3 = zeros(25)
times4 = zeros(25)
times5 = zeros(25)
for N in 1:25
    print(N)
    t = tuple(rand(N)...)
    times1[N] = @belapsed TupleTools.sort(t)
    times2[N] = @belapsed Tuple(sort!(collect(t)))
    times3[N] = @belapsed sort!(MVector(t)).data
    times4[N] = @belapsed sort(SVector(t)).data
    times5[N] = @belapsed swapsort(t)
end
plot([times1 times2 times3 times4 times5], yaxis=:log)

TupleTools.sort only has advantage at very small tuples (<=6) so my proposal is to change the method name to tuplesort and only apply it for small tuples. For such a small size it could be possible to generate fully performant codes rather than the merging algorithm.

Edit: added SortingNetworks.swapsort which is even faster than TupleTools.sort

[Jutho]

I don't fully understand your comment. No methods in TupleTools are exported or are replacing methods from Base. So TupleTools.sort (like all other methods in TupleTools) should already clearly indicate that it is acting on tuples, and I don't see what TupleTools.tuplesort would gain. And indeed, this package is primarily intended for manipulating small or average length homogeneous tuples, e.g. the strides or dimensions of a multidimensional array (which will rarely go beyond length 20). The goal of this package is to provide slightly more efficient or type stable implementations for such tuples as opposed to generic methods for iterables or indexable collections that exist in Base. In the case of sort, Base.sort does not even work on tuples without converting to a vector, and when doing this, I see from your plot (and some tests of my own) that TupleTools.sort outperforms this approach up to N=20, which I think is good enough.

More efficient algorithms are definitely conceivable, see e.g. https://github.com/JeffreySarnoff/SortingNetworks.jl, but I believe that for the purpose of TupleTools, the current implementation strikes the right balance between efficiency and simplicity/maintainability.

[putianyi889]

More efficient algorithms are definitely conceivable, see e.g. https://github.com/JeffreySarnoff/SortingNetworks.jl

Thanks for the suggestion! SortingNetworks.swapsort is even faster than TupleTools.sort. I've updated the op. Unfortunately it doesn't support keywords like lt and by.

I hope the performance issue is mentioned in the document if it's not the ultimate purpose.