3 ms·
I have explored it, see https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#in-place-partitioning https://mlochbaum.github.io/BQN/implementation/
by mlochbaum 2y ago
I have explored it, see https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#in-place-partitioning https://mlochbaum.github.io/BQN/implementation/primitive/sor....
I implemented this method in Dyalog 18.0 with BlockQuicksort-like partitioning, using vectorized comparison with bit-boolean output. It's faster than you'd expect, maybe twice as slow as regular binary search when searched values are in cache, and better once they fall out of L2. But Dyalog reverted to 17.1 for later versions so you won't see it in a new download. It'll probably make it into CBQN eventually, perhaps with radix partitioning. Note that both quicksort and radix partitioning can be done and undone in a cache-friendly way.
Unlike quicksort, there's no issue of pivot selection since you always choose the midpoint of the searched values. However, there's a complementary issue of memory if the partitions become unbalanced, because the larger partition can require saved memory of roughly the depth times the number of elements. With a bit per comparison it's bounded by the size of the input.
- mlochbaum 2y agoWasn't the best section link, last paragraph here has more detail: https://mlochbaum.github.io/BQN/implementation/primitive/sort.html#binary-search https://mlochbaum.github.io/BQN/implementation/primitive/sor...
- curiouscoding 2y agoNice overview of sorting methods, thanks for sharing! I also looked a bit into radix and distribution sort at some point over the past year, but in the end high performance sorting is actually too big of a thing to just do quickly on the side, as your post well shows :") In fact I wasn't aware of the associativity issues for radix sort. That's definitely something to keep in mind and investigate. Will definitely refer back to it once I'm looking at sorting again in more detail at some point!
- mlochbaum 2y agoI got stuck on sorting too, was working on SingeliSort (https://github.com/mlochbaum/SingeliSort https://github.com/mlochbaum/SingeliSort) for a while. The basic performance is there but I need to get serious about testing before using it. But the radix sort and counting sort should be very solid. The approach is about the same as the C code currently used in CBQN, linked below. The main complication is to reduce constant overhead for shorter arrays with a small count type and better prefix sums, interleaved SWAR for SingeliSort since it targets generic architecture and shared SIMD utilities in CBQN. Email in my Github profile, feel free to contact me any time if you'd like to talk about algorithms! 32-bit radix sort: https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grade.h#L163 https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grad... plus https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radix.h https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radi...