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/