Radix sort can be unsafe for custom types

[nalimilan]

In theory, custom types defined in packages can implement any semantics for comparison and equality operators. This means that radix sort can be incorrect even for isbits types, if the comparison operators are inconsistent with the sorting of the bit pattern.

This is particularly dangerous since package authors do not necessarily consider the possibility of using RadixSort on their types, but users may do so naively without knowing the implementation details. AFAICT the only solution to prevent potentially problematic bugs is to throw an error by default when using RadixSort on a type which is not known to support it. A trait-like function SortingAlgorithms.radixsortsafe(::Type{T}) would have to be overridden to return true for types that support it. The error message could explain this, so that it is relatively easy to fix when users know what they are doing.

[nalimilan]

Below is an example of a type for which radix sort would be incorrect. Luckily this is currently an error, but it could be made more explicit:

julia> struct ModInt
           x::Int
           mod::Int
       end

julia> Base.:(==)(x::ModInt, y::ModInt) = mod(x.x, x.mod) == mod(y.x, y.mod)

julia> a = ModInt(1, 2)
ModInt(1, 2)

julia> b = ModInt(2, 2)
ModInt(2, 2)

julia> c = ModInt(3, 2)
ModInt(3, 2)

julia> using SortingAlgorithms

julia> sort([a, b, c], alg=RadixSort)
ERROR: MethodError: no method matching uint_mapping(::Base.Order.ForwardOrdering, ::ModInt)
Closest candidates are:
  uint_mapping(::Base.Order.ForwardOrdering, ::Float64) at /home/milan/.julia/SortingAlgorithms/src/SortingAlgorithms.jl:54
  uint_mapping(::Base.Order.ForwardOrdering, ::Float32) at /home/milan/.julia/SortingAlgorithms/src/SortingAlgorithms.jl:53
  uint_mapping(::Base.Order.ForwardOrdering, ::Int128) at /home/milan/.julia/SortingAlgorithms/src/SortingAlgorithms.jl:51