[CST-2] Kolmogorov complexity - cost of sorting

[Tom Puverle]

> 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; 

That doesn't sound like a constant to me then...
O( C(N) * N ) is NOT in general equal to O( N )
When you need to compare the elements on a pair by pair
basis you will find that C(N) is lg N.
I believe what you are describing as your sorting algorithm
is radix/bucket sort, which will run in O( N ), but that's 
only true because they make assumptions about the input.


e.g. using
> 256 way splits on 32 bit integers gives 4 passes.)