Value of microeffiency (was: Re: Optimal ...)

[T. William Wells]

In article <4616 at b-tech.UUCP>, zeeff at b-tech.UUCP (Jon Zeeff) writes:
) In article <688 at clsib21.UUCP> ebg at clsib21.UUCP (Ed Gordon) writes:
) >
) >>>   A linked-list sort?
) >>>
) >>>   Once upon a time I got very tired of the slowness of the
) >>>   UNIX sort program. So I wrote a clone of it. I invented a
) >>>   whole new algorithm for it which you could call a
) >>>   linked-list merge sort.  It beat every other sort method
) >>>   that I tested hands-down.  Its only drawback is the
)
) If it's that good, perhaps someone could post a copy to comp.unix.sources,
) preferably in a form that is a plug in replacement for qsort().

That's me speaking, not Ed Gordon.  However, I might go ahead and
publish it.  There is one minor gotcha: the drawback, not copied
in the message above, is that the routine has got to get memory
for the linked list.  On virtual memory systems, this could cause
my sort to be significantly slower than on non virtual memory
systems.  There is also the overhead of actually allocating the
memory; while it ought not be significant, you never know.  (The
original implementation was on a non virtual system and the
linked list was allocated at the same time as the pointers to
the strings being sorted.)

Do you think I ought to post it over here so that you guys can
attack it before I submit a final version to the archives?  If I
do, I might also send over a qsort (created by disassembling
somebodies, I forget whose, library) that I have.  It might be
interesting to beat on both pieces of code and to compare
benchmarks of the final sort routines.