[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Matej Pfajfar wrote:

> I can't really understand the ntes I made on the minimum cost of sorting
> proof that he did using kolmogorov complexity.
>
> If you take a random permutation of N elements - than the string
> describing it this has K = nlog(n).
>
> Now suppose you can sort in << nlog(n) comparisons.
> How do you then represent the string in less than nlog(n) bits?

Assuming they are X bit integers, you can represent the string as a
sequence of KX bits. You can sort this sequence in O(KX) operations using
a radix sort.

In practice, if you want to sort a large number of, say, 32 bit integers
into order, built 256 lists. Iterate through the input list, appending
each value to the appropriate list (decided by the most significant 8
bits). Clearly linear time in the number of input values. Now repeat on
each of those 256, dividing them into 65,536 lists looking only at the 2nd
most significant octet of each - again, clearly linear time. Organised
correctly, you can do this with about 768 such intermediate lists in
existence at once, plus an output list produced as you go along.

Space cost of representing input: linear in number of inputs.
Time cost of sorting input: linear in number of inputs.

It's a little bit more complex when dealing with arbitrary length elements
in the input (peak space consumption will be 256*(2nd largest element)
lists), but the same algorithm should work.


James.