[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Jonny Graham wrote:

> But this O(n) algorithm isn't 'sorting' it's just rearranging by a fixed
>   list of swaps.

Nope. It's **NOT** a fixed list of anything. It runs through the input
some constant number of times, building progressively "more sorted" and
smaller subsets of the input, until they are all fully sorted. (The
constant number of times is determined by the size of input; e.g. using
256 way splits on 32 bit integers gives 4 passes.)

> If instead of 'cheating' with a list of swaps to do to
> sort I 'cheated' by passing it a list of the same numbers sorted, I
> could 'sort' in O(1) time by just returning the sorted version;-)

This algorithm *does* operate on arbitrary input, without prior knowledge
of the values, their order or anything else. It takes a list of integers
(or whatever you're sorting - strings, floats...) and returns that list,
sorted. That's it.


James.