Sorting(排序)
内排序与外排序：外排序需要利用辅助存储器件（硬盘等），内排序可以全部放入主存储器中。
基于比较的排序算法和不基于比较的排序算法：基于比较的排序算法时间复杂度最低为O(N * logN)，基于非比较的排序算法的复杂度下界为O(N)。
输入输出序列分散存放在各个进程当中，枚举出全部进程，使用一个全局排序，如果进程Pi枚举值小于Pj,则排序完之后Pi存放的值全都小于Pj。
每个进程存放一个元素：
每个进程存放多个元素：使用比较分裂，每个进程将他的块发送给另一个进程，每个进程合并块之后只保留合并块的适当一部分。
排序网络
比较器（递增和递减）：
双调排序
复杂度为O(logN * logN)
双调序列：循环移位之后是一个先增后减的序列
重排双调序列获得单调递增序列：
s1取得的是最小值，s2取得的是最大值，所以两个序列包含的元素都不同，且合起来就是原始序列的所有元素。s1和s2的中介点是同一个（在该处s1变为递减，s2变为递增），且因为该处s2的取值大于s1，所以整个s2的值都大于s1。这样子就完成了将一个双调序列变成两个小的双调序列。
双调排序的映射
每个进程一个元素
第i个最低有效位标号不同的线执行（logn-i +1）次比较-交换操作。
-
映射到超立方体上，只需要将标号为l的输入线映射到标号为l的进程。（每次交换都是在标号只差一位的进程上交换。）
映射到格网上
每个进程一个元素块
每个进程虚拟成n/p个进程，并行效果差
使用比较-分裂操作代替比较-交换
冒泡排序及其变体
奇偶排序
串行算法是O（n*n），并行算法是O（n）。
希尔排序
快速排序
把每个子数组分给一个进程，第一次分裂花费的时间是O（N），有N个进程，所以不是成本最优的。
用于CRCW PRAM 的并行形式
在O（1）的时间将数组划分为两个更小的数组 ：选出一个主元（每个进程都写同一个内存位置，最后的值就是主元），再得到左右两个主元（也是重复覆盖），被覆盖的值将他的参考主元修改，重复步骤。
一个坏的主元可能导致有的进程空闲的划分。如果每个进程的元素最初都均匀分布，那么就能导出一个好的主元选择方法。第一个进程的中值就是全部进程的中值。