title: Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons.
abstract: We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by atemperatureparameter. Both algorithms are simple, randomized, data-oblivious sorting algorithms, which are useful in privacy-preserving computations, but, as we show, Annealing sort is much more efficient. We show that there is an input permutation that causes Spin-the-bottle sort to require Ω(n2logn) expected time in order to succeed, and that inO(n2logn) time this algorithm succeeds with high probability for any input. We also show there is a specification of Annealing sort that runs inO(nlogn) time and succeeds with very high probability.
authors.affiliation: Dept. of Computer Science University of California, Irvine Irvine, CA 92697-3435 USA, http://www.ics.uci.edu/~goodrich/
authors.forename: Michael T
authors.initials: MT
authors.lastname: Goodrich