A note on Gray code and odd-even merge

DOI10.1016/S0166-218X(87)80006-9MaRDI QIDQ1102754zbMATH OpenFDO

Authors Gerhard Larcher, Robert F. Tichy

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(87)80006-9

zbMATH Keywords

Batcher's odd-even mergeGray codemerging algorithmssum-of-digits function

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Arithmetic codes (94B40)

Review text

For an integer n let \(\sum^{^ 2\log n}_{0}\epsilon_ j2^ j\) be its binary representation. Then the standard Gray code digits of n are defined by \(\gamma_ j(n)=\epsilon_ j(n)\) if \(j=\lfloor^ 2\log n\rfloor\), \(\gamma_ j(n)=\epsilon_ j(n)+\epsilon_{j+1}(n)\) mod 2 if \(1\leq j<\lfloor^ 2\log n\rfloor\). Furthermore \(\gamma (n):=\sum_{j}\gamma_ j(n).\) Let \(F(k)=\sum_{0\leq j<k}\gamma (j)\). The authors derive upper and lower bounds for F(k) in terms of k. As a consequence they obtain estimates for the complexity of the odd-even merge algorithm of Batcher.

Recommendations

• scientific article; zbMATH DE number 4120239
• Some remarks on the combinatories of Gray codes
• scientific article; zbMATH DE number 1933234
• Bounds on the size of merging networks
• scientific article; zbMATH DE number 4087600

Cites work

• A Note on Gray Code and Odd-Even Merge
• Data Movement in Odd-Even Merging
• scientific article; zbMATH DE number 3073163 (Why is no real title available?)
• On the Number of Stable States in a NOR Network

Cited in

(2)

• Batcher's odd-even exchange revisited: a generating functions approach
• scientific article; zbMATH DE number 4120239 (Why is no real title available?)

This page was built for publication: A note on Gray code and odd-even merge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102754)