Can I solve this problem by natural merge sort?

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

Iterate such approach till not get (1 .. N)

Example of output for N=16 and decreasing array.
4
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
15 13 11 9 7 5 3 1 16 14 12 10 8 6 4 2
13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4
9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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

Can you give me some ideas to solve this problem. I think about it very much.
Thanks

How to do it please?