Perfect Shuffle 的算法

珍爱生命，远离政治。我们继续讨论算法。

2008/04/01 补充：此算法有重大缺陷。详情请见留言部分。

一年前，我们讨论过一个算法问题， perfect shuffle ，据称是个微软面试题：

输入$a_1,a_2,\cdots,a_n,b_1,\cdots,b_n$ ，如何用$O(n)$ 的时间，$O(1)$ 的空间，将这个序列顺序改为$a_1,b_1,\cdots,a_n,b_n$ 。

那一次讨论我们翻出了问题的来源，一篇长达 12 页的论文Computing the Cycles in the Perfect Shuffle Permutation，算法那是非常的复杂，我估计贴出来都没几个人仔细看。

这一次， Xie Xie （没错，又是他 :) ）翻出了 Art of Computer Programming, Volume 3 上的一个难度为 40 分的 Merge Sort 习题：

已知数列$x_1\leq x_2\leq \cdots x_M, x_{M+1}\leq x_{M+2}\leq\cdots\leq x_n$ ，设计算法使得在线性时间，常数空间实现归并，也就是将原数组排序。

而 Perfect Shuffle 问题是可以规约到这个 Merge Sort 问题的：

mergeSort(x[1...2n]); // if this function solve Merge Sort problem
perfectShuffle(x[1...2n]): // then this solve Perfect Shuffle problem
     m <- max(x[1...2n])+1;
     x[i] <- x[i]+(2i-1)m,
     x[i+n] <- x[i+n] + 2im
     mergeSort(x[1...2n])
     x[i] <- x[i]%m

原来我还不相信这个问题会是一个面试题。现在我信了。因为那个归并排序的算法还是有些牛人会知道的。

很好很强大。

Q. E. D.