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 http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk