Subject: Re: [boost] [sort] Timsort review result
From: Soul Studios (matt_at_[hidden])
Date: 2017-06-16 22:07:49
Time complexity is not the only consideration when reviewing sorting
techniques. Smoothsort is purported to have much better time complexity
across a range of scenarios, but in reality it's cache performance is
rubbish. That's where quicksort variants and timsort work well. I
haven't investigated spreadsort personally.
On 13/06/2017 11:09 p.m., Steven Ross via Boost wrote:
> 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"?
>
> _______________________________________________
> Unsubscribe & other changes: http://listarchives.boost.org/mailman/listinfo.cgi/boost
>