The periodic balanced sorting network

DOI10.1145/76359.76362zbMATH Open0698.68042OpenAlexW2096006817WikidataQ127632010 ScholiaQ127632010MaRDI QIDQ3476271FDOQ3476271

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

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

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)

Cited In (25)

• A note on constructing binary heaps with periodic networks.
• Simulating the Bitonic Sort Using P Systems
• Fragile complexity of comparison-based algorithms
• Smoothed analysis of balancing networks
• Periodic merging networks
• Periodic merging networks
• Generic Constant-Round Oblivious Sorting Algorithm for MPC
• Counting networks with arbitrary fan-out
• Time-complexity of shear sort
• Title not available (Why is that?)
• Periodic comparator networks
• Better understanding of Batcher's merging networks
• The impact of randomization in smoothing networks
• A sequential sorting network analogous to the batcher merge
• 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
• Title not available (Why is that?)
• A super-logarithmic lower bound for hypercubic sorting networks
• Self-stabilizing smoothing and balancing networks
• Parallel sorting on Cayley graphs
• Fragile complexity of adaptive algorithms

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)