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 10:38:28

On 11/10/2014 05:33 PM, Steven Ross wrote:
>> Which "these algorithms"? ALR and AFS? If so, it would mean they are better?
> These implementations (integer_sort, float_sort, string_sort) scan to
> see if they can shrink the range; integer_sort and float_sort find the
> maximum and minimum using a fast scan across the chunk of data being
> sorted, and MSD radix sort between the actual max and min.  This
> reduces the size of the problem in many common cases while adding only
> minimal overhead in the worst case.
> string_sort does something similar, checking to see if all characters
> are identical, and if so, it skips on to the next character, only
> sorting once it encounters an actual difference.  This is useful in
> cases such as hierarchical strings, where some chunks of the key are
> all the same.  Again, the overhead of this scan is minimal.

This all sounds reasonable, but I'm not sure it's in scope for a Boost review.
The primary offering of your library is that it's faster than std::sort for
particular types of keys. There's no significant interface to discuss, or
documentation, or anything, it's mostly about better algorithm.

So the question, is who is is qualified to review your algorithm as an
algorithm - you know, formal proof of correctness, formal complexity
estimates, tests and statistical validity of them, and the quality relative
to other existing algorithms. I would not think it's a job for Boost.

If you disagree, and the review manager takes your side as well, it would
be reasonable for you to provide updated paper, starting with survey of
existing algorithms (the original paper has none, merely saying that
"Knuth was wrong about sorting" and further referring to Knuth' book published
in 1997), and have that paper reviewed here?

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