The periodic balanced sorting network

DOI10.1145/76359.76362MaRDI QIDQ3476271zbMATH OpenOpenAlexWikidataFDO

Authors Martin Dowd, Yehoshua Perl, Larry Rudolph, Michael Saks

Publication date 1989

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/76359.76362

zbMATH Keywords

arithmetic and logic structuresBatcher's networkscombinatorial algorithmscomparators networknonnumerical algorithms and problemsparallelparallel sortingperformance analysisperiodic sorting networkrecurrence equationsshuffle exchange interconnection modelworst- case analysis

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The new class of g-chain periodic sorters
• Periodic multisorting comparator networks.
• Periodification scheme: constructing sorting networks with constant period
• scientific article; zbMATH DE number 1397393
• Faster merging networks with a small constant period

Cited in

(30)

• Periodic merging networks
• The new class of g-chain periodic sorters
• Periodic comparator networks
• Better understanding of Batcher's merging networks
• A note on constructing binary heaps with periodic networks.
• Fast periodic correction networks
• Self-stabilizing smoothing and balancing networks
• Faster merging networks with a small constant period
• Periodification scheme: constructing sorting networks with constant period
• Generic constant-round oblivious sorting algorithm for MPC
• scientific article; zbMATH DE number 3885324 (Why is no real title available?)
• A sequential sorting network analogous to the batcher merge
• Time-complexity of shear sort
• On the analysis of sorting networks from the viewpoint of circuit theory
• scientific article; zbMATH DE number 1156609 (Why is no real title available?)
• A super-logarithmic lower bound for hypercubic sorting networks
• scientific article; zbMATH DE number 1852169 (Why is no real title available?)
• Fragile complexity of comparison-based algorithms
• The half cleaner lemma: constructing efficient interconnection networks from sorting networks
• Counting networks with arbitrary fan-out
• Simulating the Bitonic Sort Using P Systems
• Periodic multisorting comparator networks.
• Fast periodic correction networks.
• The impact of randomization in smoothing networks
• Fragile complexity of adaptive algorithms
• Fragile complexity of adaptive algorithms
• An 11-step sorting network for 18 elements
• Periodic merging networks
• The Morita gate is universal
• Parallel sorting on Cayley graphs

This page was built for publication: The periodic balanced sorting network

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