algorithm - Batcher Merge 如何在高层工作？

Question

我试图掌握 Batcher Sort 的概念.但是，我在网上找到的大多数资源都完全侧重于证明或低级伪代码。在查看证明之前，我想了解 Batcher Sort 的工作原理。有人可以在没有过于冗长的伪代码的情况下对 Batcher Sort 的工作原理(特别是合并)进行高级概述(我想了解 Batcher Sort 背后的想法，而不是实现它)？谢谢!

Answer 1

Batcher 的排序是 mergesort 与 Batcher 的合并。

为了合并两个数组 A 和 B，Batcher 的合并将正向顺序的 A 与反向顺序的 B 连接起来，创建一个双调数组。然后应用 Batcher 的双调排序。

Batcher 的双调排序是快速排序的近亲。它将数组分成两半，进行一些交换以确保前半部分的元素不会大于后半部分的元素，然后递归地对两半进行排序。

如果一个数组可以旋转使其元素增加然后减少，则它是双调的。根据不经意排序的零一原则，足以证明零一输入的正确性，我们现在做出该假设。可能性是

0^a 1^b 0^c = 0 ... a copies ... 0 1 ... b copies ... 1 0 ... c copies ... 0 (rotate right by c positions)

和

1^a 0^b 1^c (rotate left by a positions)

其中 a、b、c 是非负整数。双调排序首先将这个数组分成大小相等的两半 A 和 B。有两种可能性:

A = 0^w
B = 1^x 0^y 1^z

或

A = 0^w 1^x
B = 1^y 0^z

或

A = 0^w 1^x 0^y
B = 1^z

或其他三个零和一互换。 Batcher 的见解是，通过将所有 i 应用于 A[i]、B[i] 的比较器，要么 A 全为零且 B 为双调，要么 A 为双调且 B 全为 1。无论哪种方式，都满足递归排序的前提条件。

唯一不平凡的情况是

A = 0^w 1^x
B = 1^y 0^z

及其补充。如果w >= y，则A、B变为

A = 0^(w+x)
B = 1^y 0^(w-y) 1^x

所以 A 是全零，B 是双调的。如果 w < y，则

A = 0^w 1^(y-w) 0^z
B = 1^(y+z)

所以 B 是全一，A 是双调的。如果我们对 A 和 B 进行递归排序，那么它们的串联就是排序后的数组。