scandum/crumsort

A branchless unstable quicksort / mergesort that is highly adaptive.

crumsort's Issues

Discussion

Moving crumsort-related commentary from here (for anyone following along, this issue has some previous discussion).

I got distcrum to maintain candidates so it can augment them from one step to the next. The switch to a more accurate count with a square root approximation was a significant speedup, and even improves on median_of_twentyfive (so I removed it; maybe median of 15 could still be useful). After that the candidate-maintaining version is about the same, but only because I'm stuck sorting all candidates instead of sorting the new ones then merging. The commented out blit_merge_block call, with cnt rather than cnt + npiv in the quadsort before it, causes segfaults. partial_backward_merge doesn't seem to have the same problem, but of course with large enough arrays it tries to use more swap space than there is, and also segfaults.

Can't be compiled as C++

The latest version of crumsort can't be compiled as C++ code because it the main entry function takes a VAR* but should rather take a void* and then cast that in the body.

Meta algorithm

Noob question, end users would love a solution that is optimal in all cases.
As such, couldn't you detect cases where pdqsort or fluxsort are expected to be optimal and switch to them at runtime automatically ?

Edge cases suitable for counting sort

Look at this approach: alantudyk/ruby@04831f6