Sorting Algorithm

[R. Kym Horsell]

In article <wayned.0936 at wddami.spoami.com> wayned at wddami.spoami.com (Wayne Diener) writes:
\\\
>   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)_.

If *part* of an algorithm is O(n**2), and all other parts are ``<''
O(n**2) then the algorithm is O(n**2). The idea is that O signifies the
asymptotic complexity of the algorithm -- for sufficiently large
n the O(n**2) term will dominate other complexity terms regardless of 
how tiny its ``coefficient'' is wrt that of other parts of the complexity
expression.

If you want to talk an algorithm that operates with ``reasonable'' values 
of some parameter then it is a bit misleading to use the O notation.

-Kym Horsell.