On Wed, Jun 3, 2009 at 7:56 AM, Jonathan Franklin < franklin.jonathan@gmail.com> wrote:
On Wed, Jun 3, 2009 at 8:37 AM, Steven Ross <spreadsort@gmail.com> 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.