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?
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.