Hi Boost community,

 

I'd like to gauge interest in a new algorithm library: **boost::algorithm::statsort**,
a sorting algorithm with O(n log log n) average complexity on smooth distributions
(uniform, Gaussian, exponential), compared to O(n log n) for std::sort.

 

 

**The algorithm**

The idea is simple: instead of comparing elements, we use their values to place
them directly into one of sqrt(n) buckets via linear interpolation, then recurse.
Using sqrt(n) (variable) rather than a fixed bucket count reduces the recursion
depth from O(log n) to O(log log n).

This is described in detail in the accompanying publication:

  Peter Taraba, "Why would you sort when you know where things approximately
  belong?", March 2025.
  
https://www.authorea.com/users/495213/articles/1240078-why-would-you-sort-when-you-know-where-things-approximately-belong?commit=06b7d9e465d985698104a8fbfe2535fcf35c1940

 

 

 

**Measured performance** (GCC -O3, x86-64 Linux):

  n=1,000,000   uniform:      84ms → 28ms   (3.0x faster)
  n=1,000,000   Gaussian:     82ms → 34ms   (2.4x faster)
  n=1,000,000   exponential:  84ms → 24ms   (3.5x faster)
  n=10,000,000  uniform:     990ms → 466ms  (2.1x faster)

 

 

 

**API** (Boost-style, header-only, C++17):

  // Container overload
  std::vector<double> v = { ... };
  boost::algorithm::statsort(v);

  // Iterator overload
  boost::algorithm::statsort(v.begin(), v.end());

  Supports any std::is_arithmetic<T> type (int, float, double, etc.)

 

 

 

 

Is there interest in this for Boost.Algorithm? Happy to post the preliminary
submission to the vault and refine based on feedback.

 

Best,
Peter

https://orcid.org/0000-0002-8199-3723
https://randommathguy.blogspot.com/