Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons

Area of Science:

• Computer Science
• Algorithms
• Data Structures

Background:

• Sorting algorithms are fundamental in computer science.
• Randomized, data-oblivious algorithms are crucial for privacy-preserving computations.
• Existing sorting methods may not meet the efficiency or privacy requirements for all applications.

Purpose of the Study:

• To analyze the efficiency of two novel randomized sorting algorithms: Spin-the-bottle sort and Annealing sort.
• To compare their performance characteristics, particularly in terms of time complexity.
• To evaluate their suitability for privacy-preserving computations.

Main Methods:

• Introduced Spin-the-bottle sort with unrestricted randomized comparisons.
• Introduced Annealing sort with distance-bounded randomized comparisons.
• Analyzed worst-case and high-probability time complexities for both algorithms.

Main Results:

• Spin-the-bottle sort has an expected time complexity of Ω(n^2 log n) for certain permutations but achieves O(n^2 log n) with high probability.
• Annealing sort demonstrates superior efficiency, with a specification running in O(n log n) time with very high probability.
• Annealing sort is shown to be significantly more efficient than Spin-the-bottle sort.

Conclusions:

• Annealing sort offers a highly efficient and practical solution for randomized, data-oblivious sorting.
• The distance-bounded comparison strategy in Annealing sort is key to its improved performance.
• Both algorithms are viable for privacy-preserving computations, but Annealing sort is preferred for efficiency.