Why does Base only have Merge Insertion and Quick sorting algorithms?

TimSort was implemented in Base at one point and it wasn’t actually the big win that it is in Python and Java. This may be because Julia tends to organize arrays quite differently from those languages, which both use pointer-heavy data structures whereas Julia tends to use inline (immutable) data structures more. That implementation was moved into SortingAlgorithms, where it still lives. It’s quite possible that the performance characteristics are different now since Julia’s compiler has evolved quite a bit as has the hardware that people use it on.

It would be a worthwhile project for someone to figure out what the best set of algorithms for Base would be. I agree that radix sort seems like it would be a win for floats and integers. TimSort might be better for some kinds of data structures or data patterns but not others. I’m not sure what the benefit of the dual pivot quick sort algorithm is supposed to be — I vaguely recall trying it and not seeing an improvement. I don’t think anyone has tried quadsort.

14 Likes