_{1}, a

_{2}, a

_{3},…a

_{n}, b

_{1}, b

_{2}, b

_{3}, …b

_{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.

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