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

On Mar 9, 2026, at 3:08 PM, Peter Taraba via Boost <[email protected]> wrote:
> 
> 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.

I am interested in learning more about this.
Thanks for the link to the paper.

However, I suspect that “Boost.Sort” (https://github.com/boostorg/sort) might be a better place.

But if that doesn’t work out, we can discuss including it in Boost.Algorithm.

— Marshall (Boost.Algorithm maintainer)



>  
>  
> **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/

_______________________________________________
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/QSJNFYHRJMVKBFWAVHROYCQP2VRI4Z3C/