The periodic balanced sorting network

DOI10.1145/76359.76362zbMath0698.68042WikidataQ127632010 ScholiaQ127632010MaRDI QIDQ3476271

Martin Dowd, Yehoshua Perl, Michael E. Saks, Larry Rudolph

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 analysis; parallel; recurrence equations; parallel sorting; combinatorial algorithms; worst- case analysis; arithmetic and logic structures; Batcher's networks; comparators network; nonnumerical algorithms and problems; periodic sorting network; shuffle exchange interconnection model

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

05A99: Enumerative combinatorics

68P05: Data structures

Related Items

A super-logarithmic lower bound for hypercubic sorting networks, Counting networks with arbitrary fan-out, Smoothed analysis of balancing networks, Fragile complexity of comparison-based algorithms, Simulating the Bitonic Sort Using P Systems, The impact of randomization in smoothing networks, Fragile complexity of adaptive algorithms, Fragile complexity of adaptive algorithms, Parallel sorting on Cayley graphs, 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, Generic Constant-Round Oblivious Sorting Algorithm for MPC, A sequential sorting network analogous to the batcher merge