[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Jonny Graham wrote:

> I'm a bit confused as to what this O(n) algorithm is doing then.
> You wrote
> "It now makes sense, but you can also reverse the sorting with O(n) (in
> fact, precisely n) integers: just record the original position of each
> value in the output. To reverse, copy each value back to its original
> position: O(n) "unsorting" using O(n) space and time."

Someone was trying to argue "if you could sort faster than n log n, that
would mean you could magically recreate the inputs by reversing the
algorithm"; I was

> I understand this as meaning that the O(n) algorithm isn't capable of
> sorting unless it has some additional information

NO. It isn't possible to *UN*sort the data without additional information.

> - "record the original
> position of each value in the output". So this is different from an
> algorithm which takes as input *only* a list of integers (or whatever)
> and outputs them in sorted form. Is that right?

No. I was talking about the "inverse sort" algorithm someone was trying to
use in a proof by contradiction.

> Sanity check: The best we can do for sorting in the general case is
> nlogn, isn't it?

For numbers and strings, no. For some other data type, perhaps, but I
can't think of any offhand... Tom?


James.