{"id":{"repo_id":"rice","oai_identifier":"oai:repository.rice.edu:1911/104542"},"canonical_url":"https://search.dev.ndltd.org/etd/rice/oai:repository.rice.edu:1911/104542","repository":{"repo_id":"rice","name":"Rice University","base_url":"https://repository.rice.edu/server/oai/request"},"display":{"title":"An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes","abstract":"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 ).","abstract_html":"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 ).","abstract_has_math":false,"creators":["Kumar, Manoj"],"institution":"Rice University","degree_name":"Master of Science","degree_level":"Masters","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Hirschberg, Daniel S."],"committee_chairs":[],"committee_members":["Sinclair, James B.","Jump, J. Robert"],"year":1981,"date_issued":"1981","date_published":"1981","updated_at":"2026-07-24T04:10:32Z","subjects":[],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1911/104542","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Hirschberg, Daniel S."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Sinclair, James B.","Jump, J. Robert"]},{"key":"dc:creator","label":"Author","values":["Kumar, Manoj"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-12-18T21:25:10Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-12-18T21:25:10Z"]},{"key":"dc:date.issued","label":"Date","values":["1981"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Rice University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1911/104542"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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 )."]},{"key":"dc:title","label":"Title","values":["An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes"]}]}],"canonical_facts":{"dc:contributor.advisor":["Hirschberg, Daniel S."],"dc:contributor.committeemember":["Sinclair, James B.","Jump, J. Robert"],"dc:creator":["Kumar, Manoj"],"dc:date.accessioned":["2018-12-18T21:25:10Z"],"dc:date.available":["2018-12-18T21:25:10Z"],"dc:date.issued":["1981"],"dc:description.abstract":["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 )."],"dc:identifier.uri":["https://hdl.handle.net/1911/104542"],"dc:language.iso":["eng"],"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."],"dc:title":["An efficient implementation of Batcher's odd-even merge algorithm and its application in parallel sorting schemes"],"dc:type":["Thesis"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Rice University"]},"updated_at":"2026-07-24T04:10:32Z"}