无存储器冲突的并行快速排序算法*

本文在一个erewpram(exclusivereadexclusivewriteparalledrandomaccessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均o((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是o(nlogn)．