algorithm - Interleave array in constant space

Question

Suppose we have an array a1, a2,... , an, b1, b2, ..., bn.

The goal is to change this array to a1, b1, a2, b2, ..., an, bn in O(n) time and in O(1) space. In other words, we need a linear-time algorithm to modify the array in place, with no more than a constant amount of extra storage.

How can this be done?

Answer 1

This is the sequence and notes I worked out with pen and paper. I think it, or a variation, will hold for any larger n.

Each line represents a different step and () signifies what is being moved this step and [] is what has been moved from last step. The array itself is used as storage and two pointers (one for L and one for N) are required to determine what to move next. L means "letter line" and N is "number line" (what is moved).

   A   B   C   D    1   2   3   4

L  A   B   C  (D)   1   2   3   4  First is L, no need to move last N
N  A   B   C  (3)   1   2  [D]  4
L  A   B  (C)  2    1  [3]  D   4
N  A   B   1  (2)  [C]  3   D   4
L  A  (B)  1  [2]   C   3   D   4
N  A  (1) [B]  2    C   3   D   4
   A  [1]  B   2    C   3   D   4  Done, no need to move A

Note the varying "pointer jumps" - the L pointer always decrements by 1 (as it can not be eaten into faster than that), but the N pointer jumps according to if it "replaced itself" (in spot, jump down two) or if it swapped something in (no jump, so the next something can get its go!).