This paper presents bitonic sorting schemes for special-purpose parallel architectures such as sorting networks and for general-purpose parallel architectures such as SIMD and/or MIMD computers. First, bitonic sorting algorithms for shared-memory SIMD and/or MIMD computers are developed. Shared-memory accesses through the interconnection network of shared memory SIMD and/or MIMD computers can be very time consuming. A scheme is introduced which reduces the number of such accesses. This scheme is based on the parity strategy which is the main idea of the paper. By reducing the communication through the network, a performance improvement is achieved. Second, a recirculating bitonic sorting network is presented, which is composed of one level of N/2 comparators plus an /spl Omega/-network of (log N-1) switch levels. This network reduces the cost complexity to O(N log N) compared with the O(N log/sup 2/ N) of the original bitonic sorting network, while preserving the same time complexity. Finally, a simplified multistage bitonic sorting network, is presented. For simplifying the interlevel wiring, the parity strategy is used, so N/2 keys are wired straight through the network.

Two parallel sorting algorithms, GENERAL-BS and MINIMIZING-BS, which are implemented on shared-memory parallel computers, are presented in this paper. A parity strategy which gives an idea for the efficient usage of the local memory associated with each processor is introduced. The number of network accesses(or communications) of the algorithm MINIMIZING-BS is reduced by approximately one half compared with the algorithm GENERAL-BS. On the basis of decreasing the communication, the algorithm MINIMIZING-BS results in a significant improvement of performance.