Request for comments: a roadmap to faster sort() for primitive types using RadixSort

[RoyiAvital]

@Lilith

@stevengj

Something to keep in mind is that we generically encourage people to employ in-place functions like sort! in performance-critical applications, but radix sort is out-of-place so you would need to know about (and probably benchmark) it to intentionally choose sort instead.

! signals mutation, not in-place-ness. sort is guaranteed not to modify its input. sort! is guaranteed to produce a sorted array in the original input vector. Neither is guaranteed to run in place (and indeed @btime sort!(v) setup = (v=rand(["hello","world"], 1000) uses merge sort which is not in place. Radix would behave similarly to merge sort.

I wish someone created a syntax for non allocating function which is what’s really important for performance.
Something like FunName!!() maybe?
Then I’d say it would be great to make all base functions have a version which accepts pre allocated buffers from outside.

Remark: This takes discussion to a detour but it makes sense as a solution if we use allocating sort algorithm to be able to set input for the allocated buffers.