Blitsort: An ultra-fast in-place stable hybrid merge/quick sort

• blitsort

  15 700 3.9 C

  Blitsort is an in-place stable adaptive rotate mergesort / quicksort.

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.

• ram_bench

  2 112 0.0 C++

  A benchmark for random memory accesses

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

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

• crumsort

  7 314 3.6 C

  A branchless unstable quicksort / mergesort that is highly adaptive.

Blitsort is a hybrid quicksort, see title.

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

• highway

  66 3,623 9.8 C++

  Performance-portable, length-agnostic SIMD with runtime dispatch

  

Suggest a related project