Implementing parallel sorting algorithms on a linear array of transputers

This paper presents experimental results on a linear array of transputers for three parallel sorting algorithms, odd-even transposition sort, weavesort, and pipelined-merge sort. Though a significant amount of message communication is usually required for implementing sorting algorithms on any linear array of processors, in our experiments it is observed that the actual time spent for this is not a major overhead. This is because of the high communication bandwidth provided by the transputer system. Each of the three algorithms are described in a high-level parallel language. The number of message communications and merging complexities of these algorithms are analyzed and compared. We plot performance parameters, including parallel time complexities and resulting speedups, as functions of the number of processors used and the number of elements to be sorted.