好久没来贡献了，刚好有时间来，和大家交流一下。
这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
，不可能想出来。
设原来的结构为
a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
T(n) = O(n/2) + 2 * T(n / 2)
因此T(n) = O(nlogn)。
关于inplace地交换A2和B1的算法，相信大家都知道了。首先将A2B1这部分反序，设A2
长度为p，B1长度为q。反序后的部分，先将前q个元素反序，再将后面的p个元素反序。
这时原序列已经变成B1A2了。
试一下online coding。
# inplace swap A2B1 to B1A2
def rev(seq, begin, p, q):
i = begin
j = begin + p + q - 1
while i < j:
seq[i], seq[j] = seq[j], seq[i]
i += 1
j -= 1
# recursive routine to solve the main problem
# idx is the first index of the sequence
# calling solve(seq, 0, len(seq)) will solve the original problem
def solve(seq, idx, size):
n = (size - idx) / 2
if n <= 1:
return
p = int(math.floor(n / 2))
q = int(math.ceil(n / 2))
begin = idx + q
rev(seq, begin, p, q)
solve(seq, idx, q * 2)
solve(seq, idx + q * 2, p * 2)
