Abstract:
We study sorting algorithms based on randomized round-robin compar- isons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by a tem- perature parameter. 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 Ω (n2 log n) expected time in order to succeed, and that in O(n2 logn) time this algorithm succeeds with high probability for any input. We also show there is a specification of Annealing sort that runs in O (n log n) time and succeeds with very high probability.(Paper by M. Goodrich)