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

[ebg at clsib21.UUCP]

>>	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
>>	memory for the linked list.  (Actually, I'd bet that
>>	someone invented this sort before me, but at the time,
>>	I'd never heard of anything like it.)

I wrote it in 8080 assembler, not wanting to deal with overflowing to
buckets for a hash sort.  It was written to replace storing of
labels in intermediate files, and sorting to disk.  It's size was
unlimited, considering "heaping" to disk.  Today, with megs of memory
and virtual addressing (especially on UNIX), it would allow virtual
allocation of memory segments.

Similarly, any list can be defeated by having extremely ordered sets
of data, including alphabetic.  Linked list sort by hash would be
slightly slower than straight linked list sort, but eliminate the need
for overflow.

	--ed gordon (data systems associates, 513a ridgefield circle,
			clinton, ma 01510)