Given an array of 2n numbers of the following format
{a1, a2, a3,…an, b1, b2, b3, …bn}
We have to write a program to transform this into the following format.
{a1, b1, a2, b2, a3, b3, …, an, bn}
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 (n2+2*n) / 8 swap operations performed. So it’s time complexity is O(n2) and space complexity is O(1).