[draft 1] A quick & simple radix sort (with benchmarks)

radix_sort_mwe.jl

function radix_sort!(vs::AbstractVector{U}, ts::AbstractVector{U},
    BinType::Type{<:Unsigned}, bits::Unsigned, chunk_size::Unsigned) where {U <: Unsigned}

    axes(vs) == axes(ts) || error("Check failed: axes(vs) == axes(ts)")
    bits <= sizeof(U)*8 || error("Check failed: bits <= sizeof(U)")
    0 < chunk_size <= bits || error("Check failed: 0 < chunck_size <= bits")

    @inbounds begin

        counts = Vector{BinType}(undef, 2^chunk_size+1)
        mask = 2^chunk_size-1

        #vs0 = vs
        for shift in 0:chunk_size:bits-1

            counts .= zero(BinType)

            for x in vs
                idx = (x >> shift)&mask + 2
                counts[idx] += one(BinType)
            end

            sum = counts[1]
            for i in 2:2^chunk_size
                sum += counts[i]
                counts[i] = sum
            end
            #accumulate!(+, counts, counts)

            for x in vs
                i = (x >> shift)&mask + 1
                j = counts[i] += 1
                ts[j] = x
                #sortperm here
            end

            vs, ts = ts, vs

        end

        #if vs0 !== vs
        #    unsafe_copyto!(vs0, 1, vs, 1, length(vs0))
        #end

        vs#0
    end
end


using BenchmarkTools, SortingAlgorithms, Test

@testset "radix_sort" begin
    v = rand(1:1_000_000, 10_000)
    correct = sort(v)
    this = Int64.(radix_sort!(UInt32.(v), Vector{UInt32}(undef, 10_000),
        UInt16, unsigned(20), unsigned(7)))
    @test typeof(correct) == typeof(this)
    @test correct == this
    @test all(correct .=== this)

    v = rand(UInt64, 10_000)
    correct = sort(v)
    this = radix_sort!(copy(v), Vector{UInt64}(undef, 10_000),
        UInt16, unsigned(64), unsigned(8))
    @test typeof(correct) == typeof(this)
    @test correct == this
    @test all(correct .=== this)
end

b1 = @benchmark Int64.(radix_sort!(UInt32.(v), Vector{UInt32}(undef, 10_000),
    UInt16, unsigned(20), unsigned(7))) setup=(v=rand(1:1_000_000, 10_000))
println("this radix_sort! on 1:1_000_000")
display(b1)
b2 = @benchmark sort!(v) setup=(v=rand(1:1_000_000, 10_000))
println("Base.sort!() on 1:1_000_000")
display(b2)
b3 = @benchmark sort!(v; alg=RadixSort) setup=(v=rand(1:1_000_000, 10_000))
println("Base.sort!(alg=SortingAlgorithms.RadixSort) on 1:1_000_000")
display(b3)

b4 = @benchmark radix_sort!(copy(v), Vector{UInt64}(undef, 10_000),
    UInt16, unsigned(64), unsigned(8)) setup=(v=rand(UInt64, 10_000))
println("this radix_sort! on UInt64")
display(b4)
b5 = @benchmark sort!(v) setup=(v=rand(UInt64, 10_000))
println("Base.sort!() on UInt64")
display(b5)
b6 = @benchmark sort!(v; alg=RadixSort) setup=(v=rand(UInt64, 10_000))
println("Base.sort!(alg=SortingAlgorithms.RadixSort) on UInt64")
display(b6)