On the complexity of min-max sorting networks

DOI10.1016/J.INS.2011.12.008zbMATH Open1248.68179OpenAlexW2007772720MaRDI QIDQ454886FDOQ454886

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sorting in \(c \log n\) parallel steps
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sorting networks of logarithmic depth, further simplified
• Parallel database sorting
• Efficient unbalanced merge-sort
• Title not available (Why is that?)
• Optimal Conclusive Sets for Comparator Networks
• 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

Cited In (6)

• New Bounds on Optimal Sorting Networks
• Time-complexity of shear sort
• The Complexity of Sorting with Networks of Stacks and Queues
• An \(O(mn)\) algorithm for the 1-maximin problem on a network
• Title not available (Why is that?)
• Formally proving size optimality of sorting networks

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)