[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Tom Puverle wrote:

> > Sanity check: The best we can do for sorting in the general case is
> > nlogn, isn't it?
>
> Yes. However if we can assume some things about the input we can do
> better ( O(n) ). Say if the numbers are distributed evenly between
> 0 and 1,

Assuming you have N numbers evenly distributed between 0 and 1, you have
already sorted them:

for i = 0 to 1 step (1/N)
	print i;

:-)

> or in some finite range. Examples are bucket, radix and
> counting sorts.
> BUT as you said, these assume something about the input. In the
> general case we need to compare the elements and it is PROVABLE
> that we can't do better then N lg N.

This does NOT apply, however, to integers, floating point numbers,
strings of characters, or N-dimensional coordinates... to what DOES it
apply?


James.