A faster algorithm for sorting on mesh-connected computers with multiple broadcasting using fewer processors

Abstract

This paper presents an efficient parallel algorithm for sorting N data items on two-dimensional mesh connected-computers with multiple broadcasting (2-MCCMB). The algorithm uses N × N ^2/3 processors and takes 0(N ^1/3) time, whereas the previous algorithm by Chung-Horng Lung [3] uses N × N processors and takes 0(N ^l/2) time on 2-MCCMB.

Keywords:

• Sorting
• parallel algorithms
• mesh-connected computers
• broadcasting

C.R. CATEGORIES::

• C.1.2.
• F.1.2.
• F.2.2.