接下来呢？执行与合并排序相同的过程。合并时，不要从两个列表中按排序顺序选择一个元素（而是一个一个），而是掷硬币。根据掷硬币的结果，选择从第一个列表中选择元素还是从第二个列表中选择元素。

算法。

shuffle(list):
    if list contains a single element
        return list

    list1,list2 = [],[]
    while list not empty:
        move front element from list to list1
        if list not empty: move front element from list to list2

    shuffle(list1)
    shuffle(list2)

    if length(list2) < length(list1):
        i = pick a number uniformly at random in [0..length(list2)]             
        insert a dummy node into list2 at location i

    # merge
    while list1 and list2 are not empty:
        if coin flip is Heads:
            move front element from list1 to list
        else:
            move front element from list2 to list

    if list1 not empty: append list1 to list
    if list2 not empty: append list2 to list

    remove the dummy node from list

空间的关键点是将列表分为两部分不需要任何额外的空间。我们唯一需要的额外空间是在递归过程中在堆栈上维护log n个元素。

虚拟节点的意义在于要认识到，插入和删除虚拟元素可以使元素的分布保持均匀。

分析。 为什么分布均匀？在最终合并之后，P_i(n)任何给定数字最终出现在该位置的概率i如下。要么是：

• i排在自己列表的第4位，并且该列表首次赢得了抛硬币i，这种可能性为1/2^i;
• i-1排在自己列表的第一个位置，该列表赢得了 包括最后一次 掷硬币的i-1次数 ， 并且输掉了一次，这的概率是(i-1) choose 1次1/2^i；
• 在i-2它自己的列表中排在第二位，该列表赢得了 包括最后一次 掷硬币的i-2次数并输了两次，这的概率是次； __(i-1) choose 2``1/2^i
• 等等。

所以概率

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * P_j(n/2).

归纳地，您可以证明P_i(n) = 1/n。我让您验证基本情况并假设P_j(n/2) = 2/n。该术语\sum_{j=0}^{i-1} (i-1 choose j)恰好是- i-1位二进制数的数量，即2^{i-1}。所以我们得到

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * 2/n
       = 2/n * 1/2^i * \sum_{j=0}^{i-1} (i-1 choose j)
       = 1/n * 1/2^{i-1} * 2^{i-1}
       = 1/n

我希望这是有道理的。我们唯一需要的假设n是偶数，并且两个列表被统一地改组。这是通过添加（然后删除）虚拟节点来实现的。

PS我的直觉远未达到严格要求，但为防万一。想象一下，我们将1到n之间的数字随机分配给列表的元素。现在，我们针对这些数字进行合并排序。在合并的任何给定步骤中，都需要确定两个列表中哪个头较小。但是一个大于另一个的概率应该恰好是1/2，因此我们可以通过掷硬币来模拟。

PPS是否可以在此处嵌入LaTeX？