采用折叠-展开技术的一种并行排序算法

A Parallel Sorting Algorithm by Using Folding and Unfolding Techniques

给出ｎ×ｎ网孔环接式阵列处理机上的一种并行排序算法，它将ｎ×ｎ阵列上的数据折叠成ｎ×ｎ／ｋ子阵列，排序后再展开到整个ｎ×ｎ阵列上，实现ｎ×ｎ项数据的行主序排序，其平均时间复杂度为（２＋１／ｋ）ｎ＋ｏ（ｎ）．若采用ｎ×ｎ／ｋ阵列模型，且各处理器初始、结束状态允许有ｋ项数据时，该算法的平均时间复杂度只有（１＋２／ｋ）ｎ＋ｏ（ｎ）．

In this paper, we give a parallel sorting algorithm on mesh connected array processors with wraparound connections(i.e.torus). By folding data from an n×n mesh onto an n×n/k submesh, sorting, and finally unfolding back onto the entire n×n mesh, this algorithm sorts n 2 random input data items on torus into row major order in (2+1/k)n+o(n) average steps. In addition, if n×n/k mesh is used, with queue size of k, this algorithm takes (1+2/k)n+o(n) steps only.