Batcher's odd-even exchange revisited: a generating functions approach

DOI10.1016/j.tcs.2016.05.014zbMath1342.68115OpenAlexW2512188977WikidataQ114129171 ScholiaQ114129171MaRDI QIDQ290531

Prodinger, Helmut

Publication date: 1 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.05.014

zbMATH Keywords

Mellin transformgenerating functionsingularity analysisBatcher's odd-even exchange

Mathematics Subject Classification ID

Searching and sorting (68P10) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The height of multiple edge plane trees
• Mellin transforms and asymptotics: Harmonic sums
• A note on Gray code and odd-even merge
• Asymptotics of divide-and-conquer recurrences: Batcher's sorting algorithm and a minimum Euclidean matching heuristic
• Singularity Analysis of Generating Functions
• A Note on Gray Code and Odd-Even Merge
• Data Movement in Odd-Even Merging
• Digital Sum Problems for the Gray Code Representation of Natural Numbers