It is possible, but it is very complicated! A simpler O(nlogn) and O(1) space solution might be better to code and in terms of cache.
We will solve a problem different from yours, but your problem is trivial to solve once we solve that problem.
Consider the array to be
b1, a1, b2, a2, ..., bn, an
and you have to convert this to
a1, a2, ..., an, b1, b2, ..., bn
Working with indices 1 to 2n,
we see that this is given by
i -> (n+1)*i (mod 2n+1).
An O(nlogn) time O(1) space solution
We can use divide and conquer as follows.
First for some m close to n/2 convert
b1, a1, ..., bn , an
to
a1,a2,...am, b1,b2, ..bm, a(m+1), ..., an, b(m+1), ... , bn
by recursively applying to first 2m elements, and then the remaining.
Now all we need to do this cyclic shift the middle array by m spots (this can be done in O(n) time and O(1) space)
to give
a1, a2, .., am , a(m+1), ..., an, b1, b2, ..., bm, b(m+1), ..., bn.
Of course, as IVlad pointed out, this needs O(logn) stack space. We can get around that by doing the following:
We have:
b1 a1, b2 a2, .. bm am, b(m+1) a(m+1), ..., bn an
Now swap pairs in the latter part of the array to give
b1 a1, b2 a2, .. bm am, a(m+1) b(m+1), ..., an bn
Now cyclic shift the elements at odd position: b1, b2, .., bm, a(m+1), a(m+2) ..., a(n).
This gives something like
a(m+1) a1, a(m+2) a2, ..., a(2m) am, a(2m+1) b(m+1),...,an b(n-m), b1 b(n-m+1),...,bm bn
Now again swap the latter part of the array to give
a(m+1) a1, a(m+2) a2, ..., a(2m) am, b(m+1) a(2m+1),...,b(n-m) an,b(n-m+1) b1,..., bn bm
Now recursively solve the first part and second part to give
[a1 a2 ... am][a(m+1) ... a(2m)] [a(2m+1) ...an b1 b2 .. bm][b(m+1) ... bn]
This works whether 2m >= n or not.
So, this is O(nlogn) time and O(1) space algorithm.
An O(n) time O(1) space solution.
The ideas used are similar to the ideas used in the following paper:
A simple in-place algorithm for Inshuffle.
You would need to read that paper to understand the below. I suggest you also read: How to master in-place array modification algorithms?
This is basically the inverse permutation of what is solved in the paper above.
It is enough to solve this when 2n+1 is a power of 3 = (3^m say), as we can use divide and conquer after that (like the O(nlogn) solution).
Now 2n+1 and n+1 are relatively prime, so working modulo 3^m, we see that n+1 must be some power of 2. (See that paper again to see why: basically any number modulo 3^m which is relative prime to 3^m is a power of 2, again modulo 3^m).
Say n+1 = 2^k (we don't know k yet and note this is modulo 3^m).
A way to find out k, compute powers of n+1 modulo 3^m, till it becomes 1. This gives us k (and is O(n) time at most).
Now we can see that the cycles of the permutation (see above paper/stackoverflow link for what that is) start at
2^a*3^b
where 0 <= a < k, and 0 <= b < m.
So you start with each possible pair (a,b) and follow the cycles of the permutation, and this gives an O(n) time, in-place algorithm, as you touch each element no more than a constant number of times!
This was a bit brief(!) and if you need more info, please let me know.
