Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19

Subject: Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19
From: Vladimir Prus (vladimir_at_[hidden])
Date: 2014-11-10 09:07:34

On 11/10/2014 04:54 PM, Steven Ross wrote:
> I did an algorithm search in 2008 when preparing the boost submission.
> ALR came out, fairly similar to my paper.  I have not seen much
> attention paid in academia to hybrid radix sorting.

Okay, so assuming a third party were to implement a sorting algorithm for Boost.
Why they would choose your paper over the 2008 paper?

>> >I'm worried about "similar" and "adaptation" above. If I see that function
>> >whatever_sort
>> >implements an algorithm from paper N, with 200 citations, then I can assume
>> >enough
>> >people reviewed the algorithm. If that function implements an adaptation,
>> >then
>> >I'm not really sure what complexity I can expect.
> Since you've read the overview, how about just looking through the
> code and seeing if it works as described, or testing it?  Can you ever
> be sure a concrete implementation correctly applies an abstract
> concept without looking at the implementation?  These implementations
> are fast for the same reason ALR and AFS are.  They have superior
> worst-case performance because they fall back to std::sort at a size
> that optimizes worst-case performance.  The only other difference is
> that these algorithms scan to see if they can shrink the range each
> iteration, which improves performance for non-worst-case distributions
> with little impact on worst-case distributions.

Which "these algorithms"? ALR and AFS? If so, it would mean they are better?

-- 
Vladimir Prus
CodeSourcery / Mentor Embedded
http://vladimirprus.com