Radix Sort Performance Issue (100x slower than Base)

[LilithHafner]

I think this may have come up before, but I don't see an open issue, and I stumbled upon this bug again because it was the bottleneck when profiling some hypergraph generation codes that used StatseBase's countmap which uses SortingAlgorithms's RadixSort:

using SortingAlgorithms
x = [rand(1:10, 10) for i in 1:30000];
@elapsed sort.(x) # 0.015s
@elapsed sort.(x; alg=RadixSort) # 1.4s

[nalimilan]

Profiling reveals that a lot of time is spent on this line:

SortingAlgorithms.jl/src/SortingAlgorithms.jl

Line 76 in d0a9007

bin = zeros(UInt32, 2^RADIX_SIZE, iters)

This basically shows that radix sort currently isn't optimized at all for short vectors as it allocates a matrix of size 2048×6 for Vector{Int}. We could maybe adapt the algorithm depending on the input length, but an easy solution would be to fall back to QuickSort when the input is shorter than some threshold.