Sorting Algorithm

[Geoff Kuenning]

In article <wayned.0092 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.  If anyone has seen it elsewhere, I would 
> appreciate hearing about it.  None of my "guru" programmer friends,
> my professors (I'm a hardware type who went back to college to learn
> a little software) or a literature search have turned up an equivalent

Did your professors point out that you are basically just building a
binary tree in an expensive fashion?

> does the sort "in-place" (requires very little additional memory,
> other than a few more variables).  I'm not really terribly proficient
> at "Big O" analysis, but it LOOKS like it might be O(N*log(N))
> instead of O(N^2).  Anyone want to analyse it?  

Most people would consider list links to be additional memory.  As to
complexity, it depends tremendously on the cost of comparisons.  If
comparisons are costly, then the complexity is indeed O(N log N).  On
the other hand, if comparisons are cheap compared to the cost of
following pointers (e.g., you are sorting 32-bit integers), then the
complexity becomes at least O(N**2) because you will spend all of your
time chasing up and down the list to do your "binary search".  (This
shows up one of the many deficiencies in "Big O" analysis).

> The sorting is accomplished using a binary search of a linked list
> to find the the proper insertion point (just running up and down
> the pointers and dividing the list in half each time) and then 
> moving the pointers to change an item's location.

This is very similar to building a binary tree, or possibly a balanced
binary tree.  Binary tree insertion is O(N log N);  I think balanced trees
have similar complexity but I don't have a reference handy to verify this
at the moment.  The way your code does the binary search is potentially
very expensive compared to the cost of keeping the tree balanced, especially
with very large data bases.

Having said all the above, let me add that I do think your algorithm is
interesting, and it was thoughtful of you to post it.  In some situations,
your algorithm will be the superior choice, and it may also inspire some
interesting derivatives.

	Geoff Kuenning	geoff at la.locus.com	geoff at ITcorp.com