批处理合并如何在高级别上工作?

Batcher的排序是MergeSort和Batcher的合并。

要合并两个数组a和b,batcher的merge将a按正向顺序与b按反向顺序连接起来,从而创建一个双音数组。然后应用batcher的双音排序。

batcher的双音排序是quicksort的表亲。它将数组分成两半,进行一些交换以确保前半部分的元素不大于后半部分的元素,并递归地对两半进行排序。

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

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的见解是,通过对A[I],B[I]应用一个所有I的比较器,A为全零,B为双音,或者A为双音,B为全一。无论哪种方式,都满足递归排序的前提条件。

唯一不平凡的情况是

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是双音的。如果是,则

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

所以B是所有的,A是双音的。如果我们递归地对a和b排序,那么它们的连接就是排序数组。