Given an array of 2n numbers of the following format

{a

_{1}, a_{2}, a_{3},...a_{n}, b_{1}, b_{2}, b_{3}, ...b_{n}}
We have to write a program to transform this into the following format.

{a

This can be done using the following algorithm.

We iterate over the array for (n-1) times. In first iteration we swap the middle pair. In the second iteration we swap two of the middle pairs, and so on.

For example let us consider an array of 6 numbers {1,3,5,2,4,6}. Here is how the array is changed while traversing through the algorithm.

Since n = 3, the algorithm iterated just two times and a total of 3 swaps.To generalize, for some arbitrary n, there will be (n

_{1}, b_{1}, a_{2}, b_{2}, a_{3}, b_{3}, ..., a_{n}, b_{n}}This can be done using the following algorithm.

We iterate over the array for (n-1) times. In first iteration we swap the middle pair. In the second iteration we swap two of the middle pairs, and so on.

For example let us consider an array of 6 numbers {1,3,5,2,4,6}. Here is how the array is changed while traversing through the algorithm.

1 3 5 <-> 2 4 6

1 3 <-> 2 5 <-> 4 6

1 2 3 4 5 6

Since n = 3, the algorithm iterated just two times and a total of 3 swaps.To generalize, for some arbitrary n, there will be (n

^{2}+2*n) / 8 swap operations performed. So it's time complexity is O(n^{2}) and space complexity is O(1).