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: Steven Ross (spreadsort_at_[hidden])
Date: 2009-06-03 11:54:11

On Wed, Jun 3, 2009 at 7:56 AM, Jonathan Franklin <
franklin.jonathan_at_[hidden]> wrote:

> 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?

Do I have a proof for std::sort's correctness?  Are you joking?

> 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.

McIlroy, P., "Computing Systems", *Engineering* *Radix* *Sort*, Vol.
6:1, pp. 5-27, 1993.

It's a good algorithm on its own, but it was written before introsort existed.

> 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.

Agreed, but the algorithm is a hybrid radix sort optimized for worst-case
performance;
the interface is no different, and the basic technique the same as other
hybrid sorting approaches.
I changed the fallback sort and when it is called.

> 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.
>

The thought has crossed my mind.
Would it be better to submit for publication first, and to Boost second?
Care to recommend a journal?

> 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.
> ;-)
>  <http://lists.boost.org/mailman/listinfo.cgi/boost>
>

I can write one of spreadsort's worst-case performance for a paper.
It's a time-consuming task.  Anything else you need proven?
I don't see the need to prove that radix-sorting or hybrid-sorting work.
This is well established fact, and Knuth discusses such algorithms.

I personally consider software development a cross of math and engineering.
Cache optimization, memory reuse, and loop simplification has more to do
with engineering for real processors than math.