On Mar 9, 2026, at 3:08 PM, Peter Taraba via Boost <boost@lists.boost.org> 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 -- boost@lists.boost.org
> To unsubscribe send an email to boost-leave@lists.boost.org
>
https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
> Archived at:
https://lists.boost.org/archives/list/boost@lists.boost.org/message/7QK457FVEPWUIUPACJSEZ772DNF57EVV/
_______________________________________________
Boost mailing list -- boost@lists.boost.org
To unsubscribe send an email to boost-leave@lists.boost.org
https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
Archived at:
https://lists.boost.org/archives/list/boost@lists.boost.org/message/QSJNFYHRJMVKBFWAVHROYCQP2VRI4Z3C/