JUCS - Journal of Universal Computer Science 23(1): 21-41, doi: 10.3217/jucs-023-01-0021
A Logical Reconstruction of Batcher's Mergers Or: Bitonicity is a Red Herring
expand article infoRalf Hinze, Clare Martin§
‡ Radboud University, Nijmegen, Netherlands§ Oxford Brookes University, Oxford, United Kingdom
Open Access
Almost half a century after Batcher wrote his seminal paper on sorting networks, we revisit the key algorithmic design decisions for oblivious merging to rdiscover his schemes in a disciplined way. The design space of sorting networks is eplored, resulting in a systematic reconstruction of schemes that appear in the literature in various guises.
hardware design, functional programming, parallel algorithms