|
|
back to boardHow to solve this problem? Re: How to solve this problem? Can I solve this problem by natural merge sort? Re: How to solve this problem? I have WA #1 Re: How to solve this problem? 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 |
|
|