Batcher's odd-even merging network revealed

Abstract

Comparison networks offer an attractive framework for studying parallel sorting algorithms. The visual presentation of such hard-wired networks makes processes easy to conceptualize without the overhead of programming syntax or the semantic complications of concurrency. Though simple in appearance they have a surprisingly rich structure. In this pearl we delve a little into their theory.