On the complexity of min-max sorting networks

DOI10.1016/j.ins.2011.12.008zbMath1248.68179OpenAlexW2007772720MaRDI QIDQ454886

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)

Uses Software

• SORTCHIP
• GPUTeraSort

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved sorting networks with O(log N) depth
• Optimal parallel algorithms for computing convex hulls and for sorting
• The strongest model of computation obeying 0-1 Principles
• Accelerating certain outputs of merging and sorting networks
• Sorting networks of logarithmic depth, further simplified
• Sorting in \(c \log n\) parallel steps
• Parallel database sorting
• Efficient unbalanced merge-sort
• Optimal Conclusive Sets for Comparator Networks

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