Parallel Sorting Algorithm Using Multiway Merge and Its Implementation on a Multi-Mesh Network
✍ Scribed by Bhabani P. Sinha; Amar Mukherjee
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 288 KB
- Volume
- 60
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper, we present a parallel sorting algorithm using the technique of multi-way merge. This algorithm, when implemented on a t dimensional mesh having n t nodes (t>2), sorts n t elements in O((t 2 &3t+2) n) time, thus offering a better order of time complexity than the [((t 2 &t) n log n)Â2+O(nt)]time algorithm of P. F. Corbett and I. D. Scherson (1992, IEEE Trans. Parallel Distrib. Systems 3, 626 632). Further, the proposed algorithm can also be implemented on a Multi-Mesh network (1999, D. Das, M. De, and B. P. Sinha, IEEE Trans. Comput. 48, 536 551) to sort N elements in 54N 1Â4 +o(N 1Â4 ) steps, which shows an improvement over 58N 1Â4 +o(N 1Â4 ) steps needed by the algorithm in (1997, M.