A unified algorithm for sorting on multidimensional mesh-connected processors

A new algorithm is proposed for sorting on multidimensional meshes. The algorithm, called MeshSort, is significant in that it is a general algorithm that unifies 2 well-known algorithms that operate on special cases of the multidimensional mesh: 1. Bitonic sort on the binary hypercube, and 2. Shears...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1991-02, Vol.37 (4), p.225-231
Main Authors: Corbett, Peter F., Scherson, Isaac D.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Bitonic sort
Computer programming
Computer science
Computer science
control theory
systems
Exact sciences and technology
Functions
Hypermesh
Mathematical models
MeshSort
Multiprocessing
parallel algorithms
Parallel processing
Shearsort
Software
Theory
Utility programs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A new algorithm is proposed for sorting on multidimensional meshes. The algorithm, called MeshSort, is significant in that it is a general algorithm that unifies 2 well-known algorithms that operate on special cases of the multidimensional mesh: 1. Bitonic sort on the binary hypercube, and 2. Shearsort on the 2-dimensional mesh. Both Bitonic sort on a hypercube and Shearsort are shown to be special cases of MeshSort. MeshSort operates on meshes of any size and dimension. An indexing scheme is introduced that is a hybrid of the major and the snake-like indexing schemes. MeshSort is described in terms of the indexing scheme and simple sorting instructions. This provides a powerful technique for describing recursive and iterative multidimensional mesh algorithms in a concise manner. Like Bitonic sort and Shearsort, MeshShort is nonoptimal.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(91)90193-L