study on Sorting of A Parallel Computer Using Protocol in Ubiquitous Environment

Sorting can a be major bottleneck in many applications. Performance can vary by orders of magnitude, depending on how the sort operation is implemented. Parallel sorting algorithms have been developed to take advantage of distributed ubiquitous computers. But the speedup of parallel sorting algorithms decrease rapidly with increased number of processors due to parallel processing overhead such as context switching time and inter-processor communication cost. In this paper, we propose a parallel sorting method which provides linear speedup of an optimal serial algorithm for a system with a large number of processors. This algorithm may even provide superlinear speedup for a practical system. The algorithm takes advantage of an interconnection network properties and its protocol in ubiquitous environment.