Potentially interesting sorting comparison: Blitsort

[tecosaur]

Hello,

It's great to see your attempts to make sorting in Julia faster. A while ago I was trying to find the cutting edge in sorting algorithms and I ended up stumbling across https://github.com/scandum/blitsort.

It might be interesting to add that to the comparison plot, and if it compares favorably perhaps a Julia implementation may be possible? Taking the README at face value, it lists a number of desirable attributes:

• Best case O(n), worst case O(n log n)
• O(1) memory usage
• stable
• adaptive

That page also breaks down the sorting performance into different types of input, which could also be useful here I think to give a more complete picture.

E.g. (from the blitsort readme)

[LilithHafner]

Thanks! I'd be happy to review a PR adding that as a comparison.

That graph shows "the relative performance on 100,000 32 bit integers", a use case where Julia already achieves stable O(n) worst-case runtime, and outperforms standard c/c++ algorithms by more than 7x so it is unlikely that it would be a good idea to use blitsort as Julia's default in this case.