In this paper we discuss a parallel sorting algorithm on a hypercube. Its time complexity is O(n logn/p) +O(n). Here, P is the number of processors available and n, the amount of items to be sorted. Take the problem o...In this paper we discuss a parallel sorting algorithm on a hypercube. Its time complexity is O(n logn/p) +O(n). Here, P is the number of processors available and n, the amount of items to be sorted. Take the problem of time-space optimization into consideration, when P≤ O(log n), this algorithm is both timespace optimal and cost optimization. But this means only speedup is O(P) and it is not linear speedup. Therefore, we further discuss relevant parallel efficiency problems.展开更多
文摘In this paper we discuss a parallel sorting algorithm on a hypercube. Its time complexity is O(n logn/p) +O(n). Here, P is the number of processors available and n, the amount of items to be sorted. Take the problem of time-space optimization into consideration, when P≤ O(log n), this algorithm is both timespace optimal and cost optimization. But this means only speedup is O(P) and it is not linear speedup. Therefore, we further discuss relevant parallel efficiency problems.