Fragile complexity of comparison-based algorithms

DOI10.4230/LIPIcs.ESA.2019.2OpenAlexW2977709790MaRDI QIDQ5075734

Rolf Fagerberg, Manuel Penschuck, David Hammer, Ulrich Meyer, Peyman Afshani, Irina Kostitsyna, Riko Jacob, Nodari Sitchinava

Publication date: 11 May 2022

Full work available at URL: https://arxiv.org/abs/1901.02857

zbMATH Keywords

algorithmslower boundscomparison based algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Fragile complexity of comparison-based algorithms

Cites Work

• Unnamed Item
• Improved sorting networks with O(log N) depth
• Constructing sorting networks from k-sorters
• Sorting networks of logarithmic depth, further simplified
• Sorting in \(c \log n\) parallel steps
• Tail bounds for sums of geometric and exponential variables
• The periodic balanced sorting network
• Expander graphs and their applications
• Parallel Merge Sort
• Selection Networks
• Lower Bounds on Merging Networks
• A Method of Constructing Selection Networks with $O(\log n)$ Depth
• Comparator networks for binary heap construction
• Fragile complexity of comparison-based algorithms
• Zig-zag sort

This page was built for publication: Fragile complexity of comparison-based algorithms