sorting algorithm

[Geoff Kuenning]

Since a couple of people were kind enough to point out my mistakes via e-mail,
I thought I'd better publicize them so others don't blindly believe me.

First, it is incorrect to refer to the complexity of the algorithm as
"O(N log N) if pointer following is cheap, and O(N**2) otherwise."  The
complexity of the algorithm is O(N**2), period.  This has been pointed out
in another posting.  What I should have said is that the *execution time*
of the algorithm is proportional to N log N for small N and cheap pointer
following, and is proportional to N**2 otherwise.  All I can say in my
defense is that my brain gets taken out of gear during summer vacation :-)

Also, I said that insertion in a balanced binary tree is O(N log N);  it was
pointed out to me that in fact it's O(log N).  This means that "treesort"
has complexity of O(N log N).  Further, an unbalanced binary tree has
worst-case insertion complexity of O(N) [if it's completely unbalanced],
so watch out for those unbalanced trees!  However, I'm off the hook here,
since I explicitly said I wasn't sure.

Anyway, thanks to all the people who wrote with corrections.  Every one of
you was polite and helpful about it.  Who says the net is populated by
rude schmucks?

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