Batcher’s Odd-Even Merging Network Revealed
- Submitting institution
-
Oxford Brookes University
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 185946972
- Type
- D - Journal article
- DOI
-
10.1017/S0956796818000163
- Title of journal
- Journal of Functional Programming
- Article number
- e14
- First page
- -
- Volume
- 28
- Issue
- -
- ISSN
- 0956-7968
- Open access status
- Compliant
- Month of publication
- June
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This was the most downloaded paper in the Journal of Functional Programming in 2018, with almost three times as many downloads as the paper that came second. This sorting network was devised by Ken Batcher in the 1960’s, and still considered as an easy way of doing reasonably efficient sorting on a GPU. The traditional proof of correctness is index-ridden and relies on the so-called zero-one principle. This paper translates the opaque network of hardware into a purely functional representation, giving a succinct and elegant correctness proof, which reveals that Batcher’s construction builds on the monotonicity of merge itself.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
