A Logical Reconstruction of Batcher's Mergers Or: Bitonicity is a Red Herring
Ralf Hinze (Radboud University, The Netherlands)
Clare Martin (Oxford Brookes University, United Kingdom)
Abstract: Almost half a century after Batcher wrote his seminal paper on sorting networks, we revisit the key algorithmic design decisions for oblivious merging to re- discover his schemes in a disciplined way. The design space of sorting networks is ex- plored, resulting in a systematic reconstruction of schemes that appear in the literature in various guises.
Keywords: functional programming, hardware design, parallel algorithms
Categories: D.3.2, D.3.3