Should we make radix sort the primary option for sorting?

Internals & Design
1

In a typical programming language, comparison-based sorting function is typically used due to the requirements being simpler, only requiring comparisons.
In practice, however, if comparisons are possible, radix sorting is also likely possible.
Because Julia multiple dispatch paradigm allows you to know the type of the sorted objects using generic API, should we take advantage of this fact and leverage the speedup?

1 Like
2

Julia’s default sorting is not a simple algorithm but a rather complex pipeline thanks to awesome work by @Lilith :slight_smile: I highly recommend checking out her JuliaCon 2023 talk about the full sorting pipeline https://www.youtube.com/watch?v=dXkNazmV9pA.

For reference this is what it looks like in my Julia 1.10.2 and if you look closely there is a RadixSort in there for a suitable case:

julia> Base.Sort.DEFAULT_STABLE
Base.Sort.MissingOptimization(
    Base.Sort.BoolOptimization(
        Base.Sort.Small{10}(
            Base.Sort.InsertionSortAlg(),
            Base.Sort.IEEEFloatOptimization(
                Base.Sort.IsUIntMappable(
                    Base.Sort.Small{40}(
                        Base.Sort.InsertionSortAlg(),
                        Base.Sort.CheckSorted(
                            Base.Sort.ComputeExtrema(
                                Base.Sort.ConsiderCountingSort(
                                    Base.Sort.CountingSort(),
                                    Base.Sort.ConsiderRadixSort(
                                        Base.Sort.RadixSort(),
                                        Base.Sort.Small{80}(
                                            Base.Sort.InsertionSortAlg(),
                                            Base.Sort.ScratchQuickSort(missing, missing,
                                                Base.Sort.InsertionSortAlg()))))))),
                    Base.Sort.StableCheckSorted(
                        Base.Sort.ScratchQuickSort(missing, missing,
                            Base.Sort.InsertionSortAlg())))))))
10 Likes
3

Oh… Julians seem to always be one step ahead of what I do.

3 Likes