I haven't coded this problem yet.
But I think if the test is :
10000
10000 9999 9998 ... 1
It needs 9999 steps to sort this sequence,each step needs to write 10000 elements to the output file.And at last,the output file would contain at least 100000000 elements.I think it's impossible and the problem must be solved with o(N^2) .That's right?

p/s:sorry for my poor english.

No, the number of steps for this test is far less...

I didn't solve too but also have Idea.
Let seggment [a,b] is a maximal subsequence of type a...a+1..a+2...b in x[N].Let NN -number of such segment.
If NN==2 then k=1- number of sortings. I am sure that we can so organaze sort by the such way that  on each step NN:=(NN+1)/2. From this we can take formula for k and quick solution.In other words on each permutation mumber of segments should decrease in 2 times.
Now I got Ac And confirmed my idea.

Edited by author 16.12.2008 20:44