A time-space optimal parallel sorting on a hypercube

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