Re: [boost] sorting library proposal (Was: Review Wizard Status Report for June 2009)o

Subject: Re: [boost] sorting library proposal (Was: Review Wizard Status Report for June 2009)o
From: Jonathan Franklin (franklin.jonathan_at_[hidden])
Date: 2009-06-03 10:56:47

On Wed, Jun 3, 2009 at 8:37 AM, Steven Ross <spreadsort_at_[hidden]> wrote:
> Is insertion_sort to std::sort such a big
> complicated change that it can't be accepted?

Do you have a proof for it's correctness?

If not, perhaps it would be easy to modify the proof(s) for the
algorithm you modified.

> I've described the changes in string_sort vs.
> American Flag Sort already,

Is there a publication you can reference?  My apologies if you already
posted it.

> It would get expensive to publish a paper for every little tweak I've stuck in
> a sorting algorithm, so depending on publications for every improvement is a
> great way to slow down progress, especially if you demand that people cite
> said publications.

It's also very expensive to standardize on broken algorithms and interfaces.

Publishing each little tweak in a separate paper is certainly a Bad
Idea.  However, if you think the "package" is good enough for a boost
library, then it is certainly good enough for a publication.

> People seem to get the impression from his
> book that comparison-based sorting is the only general way to sort,  ...

"People" are wrong all the time.
;-)

> a worst-case fallback check (integer_sort/float_sort), falling back to
> std::sort
> an optimization for long substrings (string_sort)
> float to integer cast (float_sort)
> assorted performance tweaks
>
> Are those changes really so dangerous?

This is Math, not politics... Let's see a proof.
;-)

Jon