Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!usc!apple!uokmax!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.c
Subject: Re: Sorting Algorithm
Keywords: Sort Sorting C Source Linked-Lists
Message-ID: <3612@goanna.cs.rmit.oz.au>
Date: 24 Aug 90 01:47:19 GMT
References: <wayned.0932@wddami.spoami.com>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 51

In article <wayned.0932@wddami.spoami.com>,
wayned@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.