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 mXn/2 each, stored in an mXn 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. Next, an algorithm is presented to merge two vertically aligned subfiles, stored in a mesh-connected processor array in row-major order. Finally, a sorting scheme is proposed that requires lln route steps and 2 log n compare-exchange steps to sort n elements stored in an nXn mesh-connected processor array. The previous best sorting algorithm requires 14 n route steps ( for practical values of n, 4 < n 512 ).

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

1981

Author dc:creator

• Kumar, Manoj

Advisor dc:contributor.advisor

• Hirschberg, Daniel S.

Committee members dc:contributor.committeemember

• Sinclair, James B.
• Jump, J. Robert

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/104542

OAI identifier oai:identifier

oai:repository.rice.edu:1911/104542