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