如果我们颠倒“红框”的顺序，双调排序是否仍然有效？

Question

维基百科有一篇关于 Bitonic Sorter 的文章，其中解释了总线盒的算法。

这里，每条水平线代表待排序数组的一个元素，每个箭头代表一次交换操作，使得最大的元素放在箭头所向的方向上。我的问题是：我们可以颠倒“蓝框”内“红框”的顺序吗？即，假设最后一个蓝色框是按以下顺序执行的：

经过此更改，算法仍会对数组进行排序吗？

Answer 1

不，反转这些操作并不总是能正确地对数组进行排序。

例如，只需查看包含 4 个值的数组，这样我们就只有图像的这一部分：

现在我们考虑当我们反转较大的蓝色框中的操作时会发生什么。让我们举个例子：

[4,1,2,3]

第一阶段（列）完成后，我们得到：

[1,4,2,3]

大蓝色框的较小箭头不会带来任何变化（因为我们刚刚验证了这些对并在需要时进行了交换），因此剩下的唯一操作由较大箭头表示，这给出了以下结果：

[1,3,2,4]

所以有一个反例。

Answer 2

反转最后一个框（框 4）中的操作顺序不起作用的原因是发生了非常具体的事情。

1. 框 4 的输入是一个双调序列。

2. 框中的每个操作都会将双调序列 A 拆分为两个较小的双调序列：A1 和 A2，使得 A1 中的所有值 >= A2。例如：

    In1:  AAAAAAAA  (A must be a bitonic sequence)  
    Out1: BBBB CCCC (every element in B >= C) (and B, C are bitonic sequences)
 
    In2:  BBBB CCCC
    Out2: DD EE FF GG (every element in D >= E >= F >= G)

    In3:  DD EE FF GG
    Out3: K L M N O P Q R (K >= L >= M >= N >= O >= P >= Q >= R)
    //The sequence is now sorted.

如果你以相反的方式这样做，你就会将一个双音序列分成许多个，而那些你无法以完全相同的方式轻松组合的序列。 这种魔力之所以有效，是因为每个双调序列都递归地细分为两个小节，其中一个小节始终比另一小节包含更大的成员。

相反的过程，从多个较小的双调序列创建一个更大的双调序列，当然是可能的，这就是框 1、2 和 3 所做的。
每个盒子创建长度为 2n 的双调序列，给定长度为 n 的成对双调序列集。

您建议的更改是将时钟倒回到框 1 之前。

回顾一下：
双调排序首先创建一个长度为 n 的长双调序列。
然后，它递归地将这个长序列分成两半，使得上半部分中的所有值都大于下半部分中的值。
一旦所有部分的长度均为 1，序列就已排序。