Sorting Algorithm

[Richard A. O'Keefe]

In article <wayned.0936 at wddami.spoami.com>, wayned at wddami.spoami.com (Wayne Diener) writes:
 [I wrote]
> >So it is an O(N**2) member of the family of insertion sorts.

> A couple of points here:

> 1)  The _worst_ case number of pointer movements for each search is:
>     N/2 + N/4 + N/8 + .... = N, and it has to do it N times, yielding
>     O(N**2).  However, I believe you'll find that the average case
>     will yield O(K * log base 2 (N)) (where K is probably about 1.4)
>     number of pointer movements per element.

What we're doing is inserting elements one-by-one into an ordered
collection.  Only the order matters, so we might as well use numbers.
Suppose at some time we have M elements in the ordered collection:
	[1|2|3|...|M]
The cursor will be pointing at the last element we inserted, and since
I'm assuming uniform random input, that is equally likely to be any of
the M items.  The next item will be 0.5, 1.5, 2.5, ... M.5 each with
equal likelihood, and the cursor will have to move to the appropriate
position.  The expected distance is something like

	sum{i=1..M} sum{j=0..M} abs(i-j)
	--------------------------------
	sum{i=1..M} sum{j=0..M} 1

Either there is a mistake in my algebra (which is *very* likely)
or this works out to an average movement of about M/3, for a total
of roughly (1/6)N**2 pointer movements, *average*.

> 2) Although it yields only a constant improvement (and doesn't change
>    the Big O class), the time cost of a pointer movement is (as a 
>    normal rule) _substantially_ less than the time cost of the comparison. 

Yes, of course.  That's why list merge outperforms quicksort.

>    If the comparison is quite costly, then for reasonable numbers of N
>    (say 10K to 50K max?) the efficiency of the sort would still be
>    approximately O(N * Log(N)) _even IF the pointer movement is O(N**2)_.

You can't call something O(NlgN) when you _know_ it contains an O(N**2)
component.  Why not stick with list merge, which not only has no O(N**2)
component, but has a smaller constant factor than quicksort?
-- 
The taxonomy of Pleistocene equids is in a state of confusion.