Sorting Algorithm

[Richard A. O'Keefe]

In article <wayned.0932 at wddami.spoami.com>,
wayned at wddami.spoami.com (Wayne Diener) writes:
> I have been unable to find any references to the sorting algorithm
> used in this program.

It is a member of the _family_ of sorts known as insertion sorts
(as Wayne Diener acknowledges in the name).

> If it's original with (sic) me, I claim a copywrite on it and release
> it for use by anyone.

That's copyRIGHT, and you can't claim copyright on an algorithm,
only on a program (or, sigh, look-and-feel).  What you could try for
is a *patent*.  This is not only fairly obvious, it's Prior Art, but
that hasn't stopped some other software patents...

> I have done empirical comparisons of this sort against bubble,
> insertion, selection and queuemerge sort.  It's a lot faster than
> the first three but slower than the queuemerge sort, however, it
> does the sort "in-place" (requires very little additional memory,
> other than a few more variables).

List merge doesn't require any extra memory either, and it only requires
*half* the number of pointers per record that Bi_In_Sort requires.  If
your method isn't substantially faster than the qsort() that came with
your C compiler (which a simple list merge can beat handsomely) why bother?

The C code presented is inordinately complicated, which makes it hard to
see what is going on.  Basically, methods of inserting something into a
sequence using binary search fall foul of one of two problems:
	- if you use an array, you can *get* anywhere fast,
	  but it takes O(N) time to move other stuff out of the
	  way to *insert* anything
	- if you use a linked list, you can *insert* fast,
	  but it takes O(N) to *get* anywhere by following links.
(There is a compromise position:  use a binary tree.  Binary trees make
an excellent representation of sequences, and handle insertion well.
That would yield a variant of TreeSort.)

Wayne Diener's version of the algorithm runs into the second problem.
To be sure, it is doing O(NlgN) *comparisons*, but in order to get anywhere
it has to follow pointers O(N**2) times.  The bottle-neck is the code

	for (i = 0; i < middle; i++) {
	    current = up ? current->prev_word : current->next_word;
	    if (current == sortbound) { test = 1; break; }
	}

So it is an O(N**2) member of the family of insertion sorts.
-- 
The taxonomy of Pleistocene equids is in a state of confusion.