Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons

DOI10.1007/s00453-012-9696-5zbMath1317.68046OpenAlexW2029765430WikidataQ37586483 ScholiaQ37586483MaRDI QIDQ476439

Michael T. Goodrich

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://europepmc.org/articles/pmc3925461

zbMATH Keywords

sortingrandomized algorithmsChernoff boundsoblivious algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Randomized algorithms (68W20)

Uses Software

• FairplayMP
• Quicksort

Cites Work

• Improved sorting networks with O(log N) depth
• Sorting networks of logarithmic depth, further simplified
• Sorting in \(c \log n\) parallel steps
• Improved upper bounds on Shellsort
• Bad cases for shaker-sort
• Analyzing variants of Shellsort
• Fun-Sort -- or the chaos of unordered binary search
• Secure multi-party computation made simple
• A lower bound on the average-case complexity of shellsort
• The coupon-collector problem revisited — a survey of engineering problems and computational methods
• Universally composable two-party and multi-party secure computation
• Fault Tolerant Sorting Networks
• A Lower Bound on the Size of Shellsort Sorting Networks
• Computing with Noisy Information
• Lower Bounds for Shellsort
• Hypercubic Sorting Networks
• Analysis of Shellsort and related algorithms
• Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms
• Probability and Computing
• Quicksort
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons