A logical reconstruction of Batcher’s mergers, or, Bitonicity is a red herring
- Submitting institution
-
Oxford Brookes University
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 185749102
- Type
- D - Journal article
- DOI
-
10.3217/jucs-023-01-0021
- Title of journal
- Journal of Universal Computer Science
- Article number
- -
- First page
- 21
- Volume
- 23
- Issue
- 1
- ISSN
- 0948-695X
- Open access status
- Compliant
- Month of publication
- January
- Year of publication
- 2017
- 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 paper appeared in a JUCS Special Issue on functional programming language design and implementation. The paper uses the power of the algebraic method to derive Batcher’s mergers from minimal assumptions. The rigorous approach uncovers the resemblance between his two mergers, which turn out to be the canonical choices, and the proofs rely solely on the monotonicity property of comparison networks. This new presentation emphasises the phenomenal insight of Batcher to devise these algorithms using diagrams alone, without the benefit of program calculation afforded by this new presentation. This paper initiated a trilogy of related papers on sorting networks.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -