Title

Parallel Sorting Algorithm Using Multiway Merge And Its Implementation On A Multi-Mesh Network

Keywords

2D mesh; CREW; EREW; MIMD; Multi-Mesh; Multi-way merge; Multidimensional mesh; Odd-even merge sort; PRAM; Shear-sort; SIMD

Abstract

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 nt nodes (t>2), sorts nt elements in O((t2-3t+2)n) time, thus offering a better order of time complexity than the [((t2-t)nlogn)/2+O(nt)]-time algorithm of P. F. Corbett and I. D. Scherson (1992, IEEE Trans. Parallel Distrib. Systems3, 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 54N1/4+o(N1/4) steps, which shows an improvement over 58N1/4+o(N1/4) steps needed by the algorithm in (1997, M. De, D. Das, M. Ghosh, and P. B. Sinha, IEEE Trans. Comput.46, 1132-1137). © 2000 Academic Press.

Publication Date

1-1-2000

Publication Title

Journal of Parallel and Distributed Computing

Volume

60

Issue

7

Number of Pages

891-907

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1006/jpdc.2000.1636

Socpus ID

0042493283 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0042493283

This document is currently not available here.

Share

COinS