Just switching positions in the array:

Pattern: A1 B1 A2 B2 ... An Bn
Position of the old: 0 1 2 3 4 5 ... 2n-1
New array stores old position: 0 2 4 ... 2n-2 1 3 5 ... 2n-1

Use two array:
OldArray store the initial pattern.
NewArray stores: Old[0] Old[2] Old[4] ... Old[(n-1)*2] Old[1] Old[3] Old[5] ... Old[2n-1]}.

For (i=0; i {
NewArray[i]=OldArray[i*2]
NewArray[n+i]=OldArray[i*2+1]
}

Memory = 2n*element size
O(n)=n