On the distribution of comparisons in sorting algorithms

DOI10.1007/BF01954896zbMath0663.68078OpenAlexW1969935217MaRDI QIDQ1115198

Pravin M. Vaidya, D. S. Richards

Publication date: 1988

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01954896

zbMATH Keywords

sortinglower boundsadversaries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cites Work

• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Efficient searching using partial ordering
• An adversary-based lower bound for sorting
• Poset Measure and Saturated Partitions
• Sorting with expensive comparands
• Some Examples of Combinatorial Averaging
• A Counting Approach to Lower Bounds for Selection Problems

This page was built for publication: On the distribution of comparisons in sorting algorithms