A computer-assisted optimal depth lower bound for nine-input sorting networks

DOI10.1007/BF02090393zbMATH Open0722.68031WikidataQ56337894 ScholiaQ56337894MaRDI QIDQ3210158FDOQ3210158

Ian Parberry

Publication date: 1991

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Recommendations

• Sorting nine inputs requires twenty-five comparisons
• Optimal sorting networks
• Optimal-depth sorting networks
• New Bounds on Optimal Sorting Networks
• scientific article; zbMATH DE number 1263220

zbMATH Keywords

lower boundparallel computingsorting network

Mathematics Subject Classification ID

Searching and sorting (68P10) Network design and communication in computer systems (68M10)

Cites Work

• 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?)
• Efficient generation of the binary reflected gray code and its applications
• A Sorting Problem
• An Improved Lower Bound for Sorting Networks
• On the time required to sum n semigroup elements on a parallel machine with simultaneous writes
• Single-exception sorting networks and the computational complexity of optimal sorting network verification

Cited In (9)

• Formalizing Size-Optimal Sorting Networks: Extracting a Certified Proof Checker
• Sorting networks: to the end and back again
• Single-exception sorting networks and the computational complexity of optimal sorting network verification
• New Bounds on Optimal Sorting Networks
• Optimal-depth sorting networks
• Applying Sorting Networks to Synthesize Optimized Sorting Libraries
• Sorting nine inputs requires twenty-five comparisons
• Optimizing sorting algorithms by using sorting networks
• Formally proving size optimality of sorting networks

This page was built for publication: A computer-assisted optimal depth lower bound for nine-input sorting networks

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