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