Re: [boost] [sort] Timsort review reminder

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.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/