Interest check: Boost.Algorithm.Statsort — O (n log log n) sorting

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/

_______________________________________________
Boost mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
Archived at: https://lists.boost.org/archives/list/[email protected]/message/7QK457FVEPWUIUPACJSEZ772DNF57EVV/