Boost logo

Boost :

Subject: Re: [boost] [sort] Timsort review reminder
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2017-06-07 12:31:40

> Francisco and I are in the middle of rewriting the docs for the Sort
> library. Integrating Timsort in there once done will be relatively simple.

I really wish you'd supplied that single page already. New Boost code is
supposed to come with documentation.

> I'll be honest here: I personally would have felt this pull request
> better reviewed and handled by Boost.Sort's maintainer. It's too small
> and limited for a full fat review by the entire community unless there
> is something very controversial about it and the maintainer feels the
> community needs to invest a week into thinking about this.
> I would prefer a mini-review myself (as I agreed to do when adding new
> algorithms to the collection).but Ronald suggested I do a full review.
> My main questions are: Does anyone care about Timsort?

My sole experience with Timsort was many years ago when I was confounded
by some Python code I was writing where a sort was not scaling with
input as it should have done (it was considerably better than N log N,
and I couldn't see how that was possible).

So yes, Timsort should be in C++, preferably with std::sort() doing it
automatically when the to be sorted set is big enough to make it
worthwhile. Exactly where than cutoff is is very hard to estimate though.

And I haven't looked at the implementation, a big worry would be
exception safety and guarantees.


ned Productions Limited Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at