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

Corresponding author: Ralf Hinze ( ralf@cs.ru.nl )

© Ralf Hinze, Clare Martin.
This article is freely available under the J.UCS Open Content License.
Citation: Hinze R, Martin C (2017) A Logical Reconstruction of Batcher's Mergers Or: Bitonicity is a Red Herring. JUCS - Journal of Universal Computer Science 23(1): 21-41. https://doi.org/10.3217/jucs-023-01-0021
Open Access
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 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.
Keywords
hardware design, functional programming, parallel algorithms