那么下面的呢？执行与归并排序相同的过程。合并时，不要按排序顺序从两个列表中选择一个元素（逐一），而是抛硬币。根据抛硬币的结果选择是从第一个列表还是第二个列表中选择元素。
编辑（2022-01-12）：正如 GA1 在回答如下 https://stackoverflow.com/a/28765191/44738，该算法不会随机均匀地产生排列。
算法。
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 个元素。
虚拟节点的要点是实现插入和删除虚拟元素保持元素分布均匀。
编辑（2022-01-12）：正如莱利在评论中指出的那样，下面的分析是有缺陷的.
分析。为什么分布均匀？最终合并后的概率P_i(n)任何给定数字最终处于该位置i如下。要么是：
- in the
i- 在自己的列表中排名第，并且该列表赢得了掷硬币第一名i次，出现这种情况的概率为1/2^i;
- in the
i-1- 在自己的列表中排名第一，并且该列表赢得了掷硬币的胜利i-1 times 包括最后一张丢失一次，概率为(i-1) choose 1 times 1/2^i;
- in the
i-2-将其放入自己的列表中，并且该列表赢得了掷硬币的胜利i-2 times 包括最后一张且输了两次，则概率为(i-1) choose 2 times 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-bit 二进制数，即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是偶数，并且两个列表被均匀地打乱。这是通过添加（然后删除）虚拟节点来实现的。
附：我最初的直觉远非严格，但我列出它以防万一。想象一下，我们将 1 到 n 之间的数字随机分配给列表的元素。现在我们对这些数字进行合并排序。在合并的任何给定步骤中，它需要决定两个列表的头中哪一个较小。但其中一个大于另一个的概率应该正好是 1/2，所以我们可以通过抛硬币来模拟这一点。
附言有没有办法在这里嵌入 LaTeX？
