I solved it via following approach, split array by incrementing sub sequencies (incrementing by 1) and join it back after sorting.
For example 5 1 3 2 4 Will be splited by (5) (1 2) (3 4). After sort it by first element (5) (1 2) (3 4) => (1 2) (3 4) (5) After that all sequences on odd position gos to way #1 and all other to way #2 We will have (1 2 5) in way#1 and (3 4) in way#2 and trust order in array. we will have (5 1 2) in way#1 and (3 4) in way#2. And after join in will be (5 1 2 3 4).
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.
Is there any way to calculate k by any formula or the only way is to get it through the sorting sequence generation? I can calculate the amount of steps (and the steps themselves) to sort any input with some fixed length, but obviuosly, there are some sequences of this length, that can be sorted by shorter sequence of steps and I cannot understand how to differ them in the input.