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

performance analysiscombinatorial algorithmsparallelrecurrence equationsparallel sortingworst- case analysisarithmetic and logic structuresBatcher's networkscomparators networknonnumerical algorithms and problemsperiodic sorting networkshuffle exchange interconnection model

Mathematics Subject Classification ID

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

Recommendations

• The new class of \(g\)-chain periodic sorters
• Periodic multisorting comparator networks.
• Periodification scheme: constructing sorting networks with constant period
• Publication:4936897
• Faster merging networks with a small constant period

Cited in

(26)

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

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)