Re: [boost] [sort] Timsort review reminder

-----Original Message----- From: Boost [mailto:boost-bounces@lists.boost.org] On Behalf Of Klaim - Joël Lamotte via Boost Sent: 06 June 2017 20:09 To: Boost Developers List Cc: Klaim - Joël Lamotte Subject: Re: [boost] [sort] Timsort review reminder

On 6 June 2017 at 17:40, Zach Laine via Boost wrote:

...

Please provide a link to online documentation, if if one exists. All I've been able to find so far is a paper and Doxygen reference docs. I got that much by cloning the GitHub repo (putting docs online somewhere will get you a lot more reviewers :). Did I miss it somewhere?

Zach

On Tue, Jun 6, 2017 at 10:09 AM, Steven Ross via Boost < boost@lists.boost.org> wrote:

...

The review for C++ Timsort in Boost is ongoing and will continue through June 12. I am the review manager. The code can be found here: https://github.com/boostorg/sort/pull/12 To merge it into a local copy of the Boost.Sort library: git checkout -b ZaMaZaN4iK-feature_branch/TimSort develop git pull https://github.com/ZaMaZaN4iK/sort.git \ feature_branch/TimSort

If you want to see a proposed version of the Sort library source with Francisco's changes and Timsort included, download the zip file <https://drive.google.com/file/d/0B4s-GPKYVV0jOGx5ckJUTkZzMWM/view? usp=sharing>. Feel free to compare flat_stable_sort with Timsort.

Please answer these questions in reply to this thread:

1. What is your evaluation of the Timsort implementation? 2. What is your evaluation of the comments? 3. Did you try to use the library? With what compiler? Did you have any problems? 4. How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? 5. How familiar are you with the details of hybrid and stable sorts? 6. Would you actually use Timsort if it was in Boost.Sort? If so, how is it better than the next best alternative? 7. Do you think Timsort should be included in Boost.Sort?

Please ask Alexander Zaitsev any questions you have about Timsort for this review before submitting your final review.

Thanks,

Steven Ross

I agree, a summary of what the hell is TimSort would be useful for potential reviewers.

It is totally unacceptable for there not to be any documentation at all (even if the Wikipedia article gives good details). At the very least it should say "This is a C++ implementation of the referenced algorithm by Tim Peters." I note this in the Wikipedia article "Formal verification- In 2015, Dutch and German researchers in the EU FP7 ENVISAGE project found a bug in the standard implementation of Timsort.[8]" I think we must have a comment on if this is 'fixed' - or ? "GNU Octave's oct-sort.cc – the C++ implementation of Timsort used in GNU Octave" are there any licensing issues from 'borrowing' from this code? I see mention of documentation - is this intended to be merged into the main Boost.Sort documentation? Paul --- Paul A. Bristow Prizet Farmhouse Kendal UK LA8 8AB +44 (0) 1539 561830