[CST-2] Kolmogorov complexity - cost of sorting

[Tom Puverle]

> 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, 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.