blitsort VS ram_bench

Blitsort: A fast, in-place stable hybrid merge/quick sort\ (62 comments)

Looks like the author added the `LICENSE` file in repo root after this comment: https://github.com/scandum/blitsort/blob/main/LICENSE

This is always a great point to bring up, though. People who don't properly declare the license of their OSS projects are (either unintentionally or internionally) make it a headache for companies to use. I'm not saying it's bad to explicitly deny corporate use (via GPL, etc.). The real problem IMO is when other OSS projects vendor unlicensed code and then declare their projects to be under MIT license. Then if a corporation uses it, they're unknowingly violating the copyright of the transitive dep.

> 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.