Make an auxiliary array, and loop over the given array twice.

Get all the odds on the first round and all the evens on the second.

in 0 based indexing, swap each ith element with (2*i)th element for first half of the array, you will get the desired arrangement

I would use STL:

std::stable_partition(a.begin(), a.end(), [](int x) { return x % 2 != 0; });

Use stable partition. Stable partition rearranges in True first order. So your condition of partition should be i % 2. stable_partition(all(A), [] (int i) {return i % 2;});