Sorting on a Mesh-Connected Parallel Computer

Two algorithms are presented for sorting n^2
elements on an n X n mesh-connected processor 
array that require O(n) routing and comparison steps.
 The best previous algorithm takes time O(n log 
n).  The algorithms of this paper are shown to be optimal
in time within small constant factors.  Extensions 
to higher-dimensional arrays are also given.

CACM April, 1977

Thompson, C. D.
Kung, H. T.

parallel computer, parallel sorting, parallel merge,
routing and comparison steps, perfect shuffle. 
processor in terconnection pattern

4.32 5.25 5.31

CA770409 JB December 29, 1977  4:58 AM

2973	5	2973
2973	5	2973
2973	5	2973
3156	5	2973
2289	6	2973
2973	6	2973
3075	6	2973