Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 23 / Issue 1

available in:   PDF (132 kB) PS (237 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-023-01-0021


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