[boost] [sort] Timsort review result

Subject: [boost] [sort] Timsort review result
From: Steven Ross (spreadsort_at_[hidden])
Date: 2017-06-13 11:09:23

After reviewing the responses, I have rejected Timsort.  Here are the
reasons:

   1. No author/maintainer responses to the questions on boost (except for
   forwarding some documentation links).  We need a maintainer for all our
   source, and I'm not volunteering to maintain new functions as complex as
   Timsort.
   2. There was no response on the Timsort bug reported during the review,
   nor any tests for it.
   3. We need better tests.
   4. Francisco is including a more efficient stable sort as part of his
   additions to the library, including handling special cases like Timsort
   handles better than stable_sort does.  Francisco will maintain his code.

I'd like to note that many people THINK they are experts on sorting because
they covered it in class or may have read about it in a textbook, but most
do not understand hybrid sorts well.  As a specific example, I saw
O(N*log(N)) mentioned as the worst-case speed limit of general-case sorts,
when in fact Spreadsort beats that as described in its docs:
http://www.boost.org/doc/libs/1_61_0/libs/sort/doc/html/index.html#sort.overview.performance

Many people also don't carefully analyze for worst-case performance, which
can be tricky.

With regards to future sorting library reviews, I'll get at least a
one-page doc describing the algorithm for the review in advance, but the
boost documentation formatting is an unreasonable request for a simple
sorting function, and I don't see the value it adds for these simple
reviews.  It is useful for a full library, but we'll be integrating the
documentation into our full library after a new function is accepted.

It isn't accurate to call it a mini-review (as described here:
http://www.boost.org/community/reviews.html#Fast-Track)  because it's
reviewing completely new source we're talking about adding to the library.
That said, do you still want me to a call the upcoming one for pdqsort a
"mini-review"?