How would you swap elements (in place) of an array like [A1,A2,A3,A4,B1,B2,B3,B4] to convert it into [A1,B1,A2,B2,A3,B3,A4,B4]?

Consider A1 as 1A, B1 as 1B, A2 as 2A and so ...

Here is the correct solution for the above problem(at-least as far as I think). Time Complexity : O(n) <Edit> Given Array G[ ] = {A1, A2, A3, A4, B1, B2, B3, B4} Required Array R[ ] = {A1, B1, A2, B2, A3, B3, A4, B4} and I am assuming that the index starts with 0. So now everything had been declared and assumed. We are going to start with real stuff. In Place Shuffle Algortihm. Lets check the Initial and Final places of each element.    (" =>"  means "goes to") Cycle 1: G[0] => R[0] ----------------- Cycle 2: G[1] => R[2] G[2] => R[4] G[4] => R[1] ----------------- Cycle 3: G[3] => R[6] G[6] => R[5] G[5] => R[3] ----------------- Cycle 4 : G[7] => R[7] So there are 4 cycles in which indexes get shuffled and we get the Required Array. So now you might be wondering that: 1.How to get the next index to shuffle with? 2. When to stop? 3. How to handle the case when there are odd number of elements? Here goes the answers: Ans 1. (i) Lets say you start with index 0. First and Last element, you don't need to shuffle. (ii) for the other elements say you start with given G[i] and you need to find corresponding R[ j ].                      j = (i*2) mod(n-1); e.g. You start with index 1 (lets call it starter index) so         next index would be (1*2)mod(7) = 2,         next index would be (2*2) mod(7) = 4,         next index would be (4*2) mod(7) = 1 Ans 2: Keep repeating it till we get to the starter index. now go to the next non-visited index and repeat the above step till all the indexes are visited. Ans 3: The above algorithm works independent of number of elements in the array. Cheers!!

I am still thinking about O(n) solution. But n*log(n) is very easy if you write a simple comparator where it compares the index of A or B and then compare A < B. Use quick sort to sort it in place.

I have an idea to solve this problem in O(n*log(n)): Denote the array as C = [A1, A2, A3, A4, B1, B2, B3, B4] step 1: swap the last half of A's with the first half of B's in place, after that C is [A1, A2, B1, B2, A3, A4, B3, B4] step 2: recursively apply step 1 to the first half of C and the second half of C, until the length of C is less or equal than 2 I have wrote the implementation in C: void ev_change(int a[], int n){     if(n > 2){         //length of first part         int new_length1 = (n + 1)/2;         //length of second par         int new_length2 = n - new_length1;         //number of elements from first part, which need to be swap in this round         int num = new_length1 / 2;         int index1 = new_length1 - num;         int index2 = new_length1;         int temp;         for( ; index1 < new_length1; index1++, index2++){             temp = a[index1];             a[index1] = a[index2];             a[index2] = temp;         }         /* if the length of first part is odd, */         /* then the first element of second part should come from B */         /* for example for n = 6 the second part is [A3, B5, B6] */         /* they should be sorted as [B5, B6, A3] */         if( new_length1 % 2 == 1){             int b1 = a[index2];             for( int i = 0, i1 = index2 - 1, i2 = n - 1; i<num; i++, i1--, i2--){                 temp = a[i1];                 a[i1 + 1] = a[i2];                 a[i2] = temp;             }         a[new_length1] = b1;         }         //recursive call         ev_change(a, new_length1);         ev_change(a + new_length1, new_length2);     }     return; } We can show the time complexity is O(n*log(n)) using master theorem T(n) = 2T(n/2) + O(n) ==> T(n) = O(n*log(n))

Perhaps I'm missing something, but there seems to be fairly simply linear-time constant-space solution, similar to Shubham Mittal's: SwapArray(array x of length n): i <- 1 while i < n {   finalDest <- computeFinalDest(x[i])   while finalDest != i {     swap x[i] and x[finalDest]     finalDest <- computeFinalDest(x[i])   }   i <- i + 1 } computeFinalDest(letter c, number n): if c = a {   return 2 * n - 1 } else {   return 2 * n } The two loops almost make it look like an O(n^2) algorithm, but consider the total iterations of each loop across the entire algorithm: -The first loop goes through n iterations overall, each taking constant time (again, ignoring the inner loop for now). -The second loop will do a maximum of n iterations across the entire algorithm; it only iterates while the element at i is out of place, and each time it switches it into its correct final position. The constant space property is apparent.