Solution to rearrange the array, algorithm puzzle.

This is a solution to the rearrange array puzzle posted earlier.

A brief description:

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]$$

Hard version: Do this in-place (preferably $O(1)$ space in WORD RAM model), and O(n) time.

(Medium version: Do it in $O(n\log n)$ time, and in-place).

Solution

---

This puzzle is surprisingly difficult (the $O(n)$ time, in-place version). It seems that we should easily be able to do it, but most first approaches fail. The in-place constraint is what makes it difficult (otherwise we can just make a new array and copy the elements easily).

This puzzle was given to me when I was at Microsoft, the problem apparently being open at the time (at least within the set of people at Microsoft who came across the puzzle).

I was able to solve it, and I was encouraged (by someone on an online forum) to write a paper on it. It only took me 4 years to write, but I finally managed to write it, and it is on arxiv now.

This is the paper: A Simple In-Place Algorithm for In-Shuffle. It is only 3 pages long, and should serve as a solution :-) [ok, I am feeling a bit lazy to write it here too.]

The $\Theta(n\log n)$ version also falls out from the paper.

Please feel free to comment if you have any questions regarding the solution in the paper.