An alternative time — optimal distributed sorting algorithm on a line network

In this paper, we consider sorting problem with n elements distributed over a number of processing entities in a distributed system. We have derived an alternative, efficient algorithm with the worst case lower bound of (n -1) rounds for distributed sorting on a line network, where n is the number of processors. The proposed distributed sorting algorithm improves the performance of each processor without creating copies of (n -2) elements at intermediate processors and reduces the execution time of Sasaki´s time-optimal algorithm [A. Sasaki, A time-optimal distributed sorting algorithm on a line network, Inform. Process. Lett., 83(2002) pp. 21-26]. Also all processors do not necessarily perform the disjoint comparison-exchange operations and simulation results show that the proposed algorithm results in better execution time with the identity of processors. This algorithm could also be extended for sorting the distributed elements on the linear embedding obtained from a general network.