Re: Proposing statsort for Boost.Sort

Some progress:

https://github.com/drpt78/statsort

I am not finished cleaning up some mess, which is there... Give me more time to polish code before review... Merci :)

Best,

Peter

Sent: Sunday, March 22, 2026 at 8:39 AM

From: "Francisco José Tapia via Boost" <[email protected]>

To: "Boost developers' mailing list" <[email protected]>

Cc: "Francisco José Tapia" <[email protected]>

Subject: [boost] Re: Proposing statsort for Boost.Sort

Algorithms have two sides, just like coins. On one side is the end user,

who wants an algorithm that’s fast and uses few resources. And on the other

side are we, the algorithm developers. In my previous message, I spoke from

the user’s perspective.

I see you’re talking about statistical methods and interpolation. I’m not a

mathematician or a data scientist, so I don’t have enough knowledge to

contribute anything to statsort.

But I encourage you to keep searching and trying. No one gets different

results by doing the same thing as everyone else. In my experience, good

results come after a fair number of attempts.

In any case, if what you’re working on is a sorting algorithm, you know it

will be judged by its speed and the resources it consumes. If it’s

something else, I’ll keep quiet.

I’d like for you to feel valued for what you’ve done and encouraged for

having tried by the end of all this. This is difficult and very demanding.

Sincerely,

Francisco Tapia

El mar, 17 mar 2026 a las 15:44, Kostas Savvidis via Boost (<

[email protected]>) escribió:

>

>

> > On Mar 17, 2026, at 16:40, Kostas Savvidis <[email protected]> wrote:

> >

> >

> >

> >> On Mar 16, 2026, at 10:21, Arnaud Becheler via Boost <

> [email protected]> wrote:

> >>

> >> why not allow users to

> >> supply a CDF estimate that actually match their actual data

> distribution?

> >> For Gaussian mixture, you would inject the mixture CDF.

> >

> > My understanding is that this family of methods of sorting optimally

> relies on knowledge of

> > inverse CDF. I am not aware of a closed form expression for inverse CDF

> for mixture of gaussians.

> >

> > I have toyed with the idea of creating a sort routine that could do live

> estimation of the inverse CDF

> > as it is traversing the list. In my mind, the difficult part is making

> sure that partially pre-sorted input would not produce much worse

> performance than unsorted.

> >

> > Also, I wander what happens to performance when the data is slightly

> different from assumed distribution? Peter?

> >

> >

> > Cheers,

> > Kostas

>

> Delete that message :-) indeed you need the CDF, not inverse. I dont know

> what I was thinking when I was typing....

> _______________________________________________

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

>

_______________________________________________

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

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