A Lower Bound on the Size of Shellsort Sorting Networks

DOI10.1137/0222006zbMATH Open0766.68021OpenAlexW2012511435MaRDI QIDQ4037684FDOQ4037684

Authors: Robert Cypher 

Publication date: 16 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222006

Recommendations

• Lower Bounds for Shellsort
• A lower bound for sorting networks based on the shuffle permutation
• scientific article; zbMATH DE number 1256658
• A new upper bound for Shellsort
• The Worst Case in Shellsort and Related Algorithms

zbMATH Keywords

lower boundssorting networkparallel sortingshellsort

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Cited In (6)

• Analysis of Shellsort and related algorithms
• Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
• Toward a lower bound for sorting networks
• A lower bound for sorting networks based on the shuffle permutation
• Bounds on the size of test sets for sorting and related networks
• A super-logarithmic lower bound for hypercubic sorting networks

This page was built for publication: A Lower Bound on the Size of Shellsort Sorting Networks

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