crumsort VS ram_bench

Blitsort is a hybrid quicksort, see title.

It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort

https://github.com/scandum/crumsort claims better performance than pdqsort

Any chance you could comment on fluxsort[0], another fast quicksort? It's stable and uses a buffer about the size of the original array, which sounds like it puts it in a similar category as glidesort. Benchmarks against pdqsort at the end of that README; I can verify that it's faster on random data by 30% or so, and the stable partitioning should mean it's at least as adaptive (but the current implementation uses an initial analysis pass followed by adaptive mergesort rather than optimistic insertion sort to deal with nearly-sorted data, which IMO is fragile). There's an in-place effort called crumsort along similar lines, but it's not stable.

I've been doing a lot of work on sorting[2], in particular working to hybridize various approaches better. Very much looking forward to seeing how glidesort works.

[0] https://github.com/scandum/fluxsort

[1] https://github.com/scandum/crumsort

[2] https://mlochbaum.github.io/BQN/implementation/primitive/sor...

> Radix sort is theoretically O(N),

Nothing theoretical about it: Sorting a list of all IP addresses can absolutely and trivially be done in O(N)

> in reality you can't do better than O(log N)

You can't traverse the list once in any sort must be ≥N.

> but memory access is logarithmic

No it's not, but it's also irrelevant: A radix sort doesn't need any reads if the values are unique and dense (such as the case IP addresses, permutation arrays, and so on).

> Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench

It's not that either.

The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. If you give that program enough memory (I have around 105gb free) it produces a silly graph that looks nothing like O(√N): https://imgur.com/QjegDVI

The latency of accessing memory is not a function of N.