On the complexity of min-max sorting networks

DOI10.1016/J.INS.2011.12.008MaRDI QIDQ454886zbMATH OpenOpenAlexFDO

Authors Giuseppe Campobello, Giuseppe Patanè, Marco Russo

Publication date 10 October 2012

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2011.12.008

zbMATH Keywords

FPGAsorting networksmerging networksmin-max circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Recommendations

• A sequential sorting network analogous to the batcher merge
• Optimal sorting networks
• New Bounds on Optimal Sorting Networks
• An 11-step sorting network for 18 elements
• Sorting networks: to the end and back again

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 53772 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1263220 (Why is no real title available?)
• scientific article; zbMATH DE number 1559567 (Why is no real title available?)
• scientific article; zbMATH DE number 826245 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• Accelerating certain outputs of merging and sorting networks
• Efficient unbalanced merge-sort
• Improved sorting networks with O(log N) depth
• Optimal Conclusive Sets for Comparator Networks
• Optimal parallel algorithms for computing convex hulls and for sorting
• Parallel database sorting
• Sorting in \(c \log n\) parallel steps
• Sorting networks of logarithmic depth, further simplified
• The strongest model of computation obeying 0-1 Principles

Cited in

(7)

• Formally proving size optimality of sorting networks
• The Complexity of Sorting with Networks of Stacks and Queues
• New Bounds on Optimal Sorting Networks
• Time-complexity of shear sort
• An \(O(mn)\) algorithm for the 1-maximin problem on a network
• Applying sorting networks to synthesize optimized sorting libraries
• scientific article; zbMATH DE number 1852169 (Why is no real title available?)

Describes a project that uses

Uses Software

• SORTCHIP
• GPUTeraSort

This page was built for publication: On the complexity of min-max sorting networks

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