Input integer array:

 a[8] = { a1, a2, a3, a4, b1, b2, b3, b4 }

Output array:

 a[8] = { a1, b1, a2, b2, a3, b3, a4, b4 }

Forget all corner cases, make sure your solution works for any int array of size 2n. You can use one or two temp variables for looping or anything, but you shouldn't use any temp arrays/stacks/queues etc to store entire array or part of array.

I'm able to get answer in O(n*log n), but I'm looking for better solution.