Batcher归并网络是Batcher提出来的，由一系列Batcher比较器（Batcher's Comparator）组成的。Batcher比较器是指在两个输入端给定输入x, y，再在两个输出端输出最大值和最小值。Batcher归并网络采用了分而治之策略，即把得到两个序列各分成两半，前一半先进行分类，后一半同样进行分类，得到两个有序的子序列，再利用归并网络进行归并。

Batcher归并网络是利用归并排序的方法可以方便地构造出排序网络。如果排序网络采用奇偶归并构造而成，我们称之为奇偶排序网络如果排序网络采用双调归并构造而成，则称之为双调排序网络采用归并方法构造排序网络的具体步骤如下：

首先对长度为n的输人序列进行两两比较，形成若干长度为2的有序序列；

使用归并方法对长度为2的有序序列进行归并，得到若干长度为4的有序序列，归并的方法为上述的奇偶归并或双调归并；

重复上述步骤，直到得到一个完整的长度为的有序序列为止1。

输入两个已排好序的序列，对这两个序列进行归并排序，在串行算法中的时间复杂度为O(n)。在并行计算中可以用奇偶归并算法来实现的。以输入的两个4元素有序序列为A和B为例，首先将这两个序列进行逆洗牌（Unshuffle）得到两个序列：其中一个是由A,B中奇数号元素组成的序列，记作奇序列OM，另一个则是由A,B中偶数号元素组成的序列，记作偶序列序列EM。接着将OM送入（2,2）奇归并器中，将EM送入（2,2）偶归并器中。于是得到一组有序的奇序列和一组有序偶序列。最后除了奇序列一个元素之外将这两个序列进行洗牌（Shuffle）比较操作即可得到一个有序序列。

算法的递归性：一个n阶的归并器是由两个n/2阶的归并器加一个洗牌比较网络构成的。比如上面的两个（2,2）归并器和最后的洗牌比较网络就构成了一个（4,4）的归并器。

一个四阶奇偶归并的例子：假设归并前的的序列是（1,5,7,6）和（2,3,4,9），那么第一次操作就将（1,2,7,4）送入（2,2）归并器中归并，得到结果为（1,2,4,7）；（5,3,6,9）送入（2,2）归并器中归并，得到结果为（3,5,6,9），接着将这两个排号序的序列进行洗牌比较：(1,32,54,67,9)=>(1,2,3,4,5,6,7,9)。

可以证明这个算法是正确的，我们要用到高德纳（Donald Ervin Knuth）的0-1原理，我们发现，对于输入的任意两个有序的0,1序列，奇序列与偶序列正好相差0个，1个或2个0。由于奇序列的第一个元素不参与最后的洗牌比较，所以参与比较的0,1数偶只有0个或1个，所以对0,1序列一定能够得到正确的排序。故而对任意的序列，奇偶归并网络可以产生正确的排序。

双调归并网络是基于Batcher定理而构建的。Batcher定理是说将任意一个长为2n的双调序列A分为等长的两半X和Y，将X中的元素与Y中的元素一一按原序比较，即 与 比较，将较大者放入MAX序列，较小者放入MIN序列。则得到的MAX和MIN序列仍然是双调序列，并且MAX序列中的任意一个元素不小于MIN序列中的任意一个元素。根据这个原理，我们可以将一个输入的n元素双调序列首先通过洗牌比较操作得到一个MAX序列和一个MIN序列，然后通过两个n/2阶双调归并器处理就可以得到一个有序序列。这个算法也是递归的，因为n阶的双调归并器是由一个洗牌比较网络两个n/2阶的双调归并器组成的。

所谓双调序列（Bitonic Sequence）是指由一个非严格增序列X和非严格减序列Y（其中X的最小元素正好是Y的最大元素）构成的序列，比如序列（23,10,8,3,5,7,11,78）。定义：一个序列a1,a2,…,an是双调序列（Bitonic Sequence），如果：

存在一个ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立；

或者序列能够循环移位满足条件（1）。

并行计算（parallel computing）一般是指许多指令得以同时进行的计算模式。在同时进行的前提下，可以将计算的过程分解成小部分，之后以并发方式来加以解决。

计算机软件可以被分成数个运算步骤来运行。为了解决某个特定问题，软件采用某个算法，以一连串指令运行来完成。传统上，这些指令都被送至单一的中央处理器，以循序方式运行完成。在这种处理方式下，单一时间中，只有单一指令被运行(processor level: 比较微处理器，CISC, 和RISC，即流水线Pipeline的概念，以及后来在Pipeline基础上以提高指令处理效率为目的的硬件及软件发展，比如branch-prediction, 比如forwarding，比如在每个运算单元前的指令堆栈，汇编程序员对programm code的顺序改写)。并行运算采用了多个运算单元，同时运行，以解决问题。相对于串行计算，并行计算可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。以程序和算法设计人员的角度看，并行计算又可分为数据并行和任务并行。数据并行把大的任务化解成若干个相同的子任务，处理起来比任务并行简单。

空间上的并行导致两类并行机的产生，按照麦克·弗莱因（Michael Flynn）的说法分为单指令流多数据流（SIMD）和多指令流多数据流（MIMD），而常用的串行机也称为单指令流单数据流（SISD）。MIMD类的机器又可分为常见的五类：并行向量处理机（PVP）、对称多处理机（SMP）、大规模并行处理机（MPP）、工作站机群（COW）、分布式共享存储处理机（DSM）。

本词条内容贡献者为: