Proposing statsort for Boost.Sort

Hi Boost.Sort maintainers,

I'm Peter Taraba, and I've been developing a new sorting algorithm called statsort that I'd love to explore adding to Boost.Sort.

I recently posted to the Boost mailing list about it, and Marshall (Boost.Algorithm maintainer) kindly suggested that Boost.Sort might be a more natural home — so here I am!

**The algorithm**

Instead of comparing elements, statsort uses their values to place them directly into one of sqrt(n) buckets via linear interpolation, then recurses until certain treshold is reached. Using sqrt(n) variable buckets (rather than a fixed count) reduces recursion depth from O(log n) to O(log log n), giving O(n log log n) average complexity on smooth distributions like uniform, Gaussian, and exponential.

Full details are in my paper:

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

Algorith in Github:

https://github.com/drpt78/statsort

**Benchmarks** (GCC -O3, x86-64 Linux, vs std::sort):

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)

The implementation is header-only, C++17, and supports any std::is_arithmetic type. It includes a fallback to std::sort for adversarial or skewed inputs to avoid worst-case degradation.

I'd love to hear your thoughts on whether statsort would be a good fit for Boost.Sort, and what steps I should take to move forward. Happy to share the code and discuss further!

Best,

Peter (and Claude AI)

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