论文部分内容阅读
本文在一个ＥＲＥＷ ＰＲＡＭｅｘｃｌｕｓｉｖｅ ｒｅａｄ ｅｘｃｌｕｓｉｖｅ ｗｒｉｔｅ ｐａｒａｌｌｅｄ ｒａｎｄｏｍ ａｃｃｅｓｓ ｍａｃｈｉｎｅ）上提出一个并行快速排序算法，这个算法用Ｋ个处理器可将Ｎ个项目在平均Ｏ（ｎ／ｋ＋ｌｏｇｎ）ｌｏｇｎ）时间内排序，所以平均来说算法的时间和处理器数量的乘积对任何ｋ≤ｎ／ｌｏｇｎ是Ｏ（ｎｌｏｇｎ）。