Rearrange the array, algorithm puzzle

This is one of my favourite algorithm puzzles.

Suppose you are given an array of $2n$ objects

$$[a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n] $$

You need to reorder the array to be

$$[b_1, a_1, b_2, a_2, \dots, b_k, a_k, \dots, b_n, a_n] $$

The algorithm should be in-place: i.e. space usage must be $O(\log^k n)$ words (in the WORD RAM model), for some constant $k$ (preferably $O(1)$ space, but $k \le 2$ will do too). Assume that each object ($a_i$ or $b_i$) takes up $O(1)$ space and copying them around is $O(1)$ time and space.

Medium:

Can you give an $O(n \log n)$ time algorithm?

Hard:

Can you give an $O(n)$ time algorithm?


[Solution]