基于散列和归并技术的有效并行排序方法

Efficient Parallel Sorting Based on Hashing and Merging Technology

本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法：将长度为ｎ的待排序数据划分成ｐ个长度为ｎ／ｐ的子序列，引入散列技术并行地对这ｐ个子序列的数据进行二次散列排序，这一阶段所需的平均时间为Ｏ（ｎ／ｐ）；最后并行地将ｐ个有序子序列归并成一个长度为ｎ的有序序列，归并阶段所需的时间为Ｏ（ｎ－ｎ／ｐ）。整个排序算法的并行执行代价为Ｏ（ｎｐ）。本排序方法可以拓广到网络并行机群环境。

An efficient parallel sorting algorithm,which is implemented on a shared memory multiprocessor system,is presented.The sequence that has n elements to be sorted are partitioned to p subsequences(length n/p ).First the p subsequences are sorted in parallel by 2 hashing,its average time is O( n/p ).Then the p sorted subsequences are merged in parallel to a sorted sequence(length n ),its time is O( n-n/p ).The total parallel execution cost is O( np ).This scheme can be extended to the network environment of parallel computers.