二维网格上的一个快速并行分类算法

A QUICK PARALLEL ALGORITHM FOR SORTING ON A TWO DIMENSION MESH

摘要: 文中采用递归分治的策略，构造了Ｎ×Ｎ网格上分类Ｎ个元素的一个快速并行算法．该算法总共需３Ｎ＋Ｏ（Ｎ１／３ｌｏｇＮ）步，每步至多做一次比较交换操作．由于Ｎ×Ｎ网格上的分类Ｎ个元素的并行算法的时间下界是３Ｎ－Ｏ（Ｎ）步，因此，该算法已近似地达到最优，而且直观简洁．

Abstract: Using the divide and conquer strategy recursively, a quick parallel algorithm for sorting N elements on a N×N mesh is presented. It needs totally 3 N+O（N 1/3 log N） steps. Each step includes one comparison and one exchange at most. Because a low bound of steps needed by sorting N elements on N×N mesh is 3 N-O(N ,the algorithm is nearly optimal.