2. 不同处理器上的元素如何进行大小比较

　　比较操作和位置交换操作是排序算法中的基本操作，它们在串行程序中都很容易实现，因为要比较大小或交换位置的两个元素都在存储空间中。而在并行算法中，这些操作并不是想象的那么容易，因为两个元素分别位于不同的结点上。

　　考虑一种极端的情况，待排序的元素与处理器的个数一样多，这样每个处理器上存储一个待排序元素。假定在算法执行过程中，两个处理器P_i和P_j要比较它们的元素a_i和a_j，比较结束后，P_i上要存储两个元素中较小的一个，而P_j则存储较大的一个。如何完成比较呢？两个处理器可以分别把自己所存储的元素发送给对方，然后每个处理器收到对方的数据后开始在本地完成比较，P_i留下较小的一个，而P_j则留下较大的一个，见图6.2.1。可见，并行算法中每个比较+交换操作需要一个比较步骤和一个通信步骤。
　　　　　
　　设通信启动时间为T_s，传输单位数据所消耗的时间是Tw（见前面的章节）。两个相邻的处理器之间交换一个元素需要T_s+T_w的通信时间（设待排序数据的大小为一个字）。通信时间相比元素比较时间而言占主导地位，所以以这种方式进行并行排序效率很低。

　　再来考虑处理器数目比较少的情况，这是每个处理器上存储多个待排序元素。设处理器个数为p，待排序元素数目为n，则每个处理器上平均有n/p个元素。定义每个处理器上的所有元素为一个超元素，定义超元素之间的大小关系。当一个超元素E₁中的所有元素都不大于另一个超元素E₂中的任何元素时，定义为E₁≤E₂。同理定义等于（=）、小于等于（≥）等关系。与普通元素不同的是，两个超元素之间可能不是≥、＝、≤中的任何一个。容易验证，超元素之间的≤关系满足传递性。来看两个编号相邻的处理器之间如何进行元素比较。与每个处理器上一个元素的情形类似，每个处理器把超元素发给对应的处理器，每个处理器在接受到对方的超元素后，合并两个超元素并排序（归并排序），然后P_i取值较小的一半，而P_j则取值较大的一半。整个过程分四步：通信-比较-合并-拆分，参见图6.2.2。
　　　

　　假设任何两个相邻编号处理器在通信网络层次上都相邻，则每次比较操作的通信开销是T_s+T_w^*n/p。当待排序的元素数目n与处理器数目p的比值足够大时，T_s可以忽略不计，对两个内部已经排序的超元素进行分布式归并排序的开销是 。