Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T23:29:04.812Z Has data issue: false hasContentIssue false
  • English
  • Français

Batcher's odd-even merging network revealed

Part of: JFP Functional Pearls

Published online by Cambridge University Press:  04 June 2018

RALF HINZE  and
CLARE MARTIN
RALF HINZE
Affiliation:
Institute for Computing and Information Sciences, Radboud University, Nijmegen 6525EC, The Netherlands (e-mail: ralf@cs.ru.nl)
CLARE MARTIN
Affiliation:
Department of Computing and Communication Technologies, Oxford Brookes University, Wheatley, Oxford OX33 1HX, UK (e-mail: cemartin@brookes.ac.uk)
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Functional Pearl
Information
Journal of Functional Programming , Volume 28 , 2018 , e14
Copyright
Copyright © Cambridge University Press 2018 

References

Batcher, K. E. (1968) Sorting networks and their applications. In Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference. AFIPS '68 (Spring), ACM, pp. 307–314.Google Scholar
Bove, A. & Coquand, T. (2006) Formalising bitonic sort in type theory. In Types for Proofs and Programs, Filliâtre, J.-C., Paulin-Mohring, C. & Werner, B. (eds), Lecture Notes in Computer Science, vol. 3839. Berlin, Heidelberg: Springer, pp. 82–97.Google Scholar
Day, N. A., Launchbury, J. & Lewis, J. (1999) Logical abstractions in Haskell. In Proceedings of the 1999 Haskell Workshop.Google Scholar
Feijen, W. & Bijlsma, L. (1990) Exercises in formula manipulation. In Formal Development of Programs and Proofs, Dijkstra, E. W. (ed). Addison-Wesley Longman Publishing Co., Inc, pp. 139–158.Google Scholar
Hinze, R. (2009) Functional pearl: la tour d'Hanoï. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP '09), Tolmach, A. (ed), ACM. pp. 3–10.Google Scholar
Knuth, D. E. (1998) The Art of Computer Programming, Volume~3: Sorting and Searching. 2nd ed. Addison-Wesley Publishing Company.Google Scholar
Reynolds, J. C. (1983) Types, abstraction and parametric polymorphism. In IFIP Congress, Mason, R. (ed), pp. 513–523.Google Scholar
Wadler, P. (1989) Theorems for free! In Proceedings of the 4th International Conference on Functional Programming Languages and Computer Architecture. FPCA '89, ACM, pp. 347–359.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.