An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting Schemes

An algorithm is presented to merge two subfiles of size n/2 each, stored in the left and the right halves of a linearly connected processor array, in 3n/2 route steps and log n compare-exchange steps. This algorithm is extended to merge two horizontally adjacent subfiles of size m × n/2 each, stored in an m × n mesh-connected processor array in row-major order, in m + 2n route steps and log mn compare-exchange steps. These algorithms are faster than their counterparts proposed so far.