快排序并行算法的N值问题

杨艳

[摘要]本文在一个PRAMCRCW（paralled random accessmachin concurrent read concurrent write）上详细的介绍了并行快速排序算法，并在此基础上提出了利用归并排序和快速排序相结合的新算法，解决了快速排序并行算法里处理器个数的N值问题。这个算法将长度为n的待排序数据利用域划分分成长度为p的子序列，在时间复杂度为O（2logp+logk）情况下得到有序序列。

[关键词]并行算法；快速排序算法；归并排序；二叉树；中序遍历

[中图分类号]F224-39 [文献标识码]A [文章编号]1672-5158（2013）06-0121-02