Randomized Shellsort: A Simple Oblivious Sorting Algorithm

In this paper, we describe a randomized Shellsort algorithm. This algorithm is a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O ( n log n ) time and succeeds in sorting any given input permutation with very high probability. Taken together, these properties imply applications in the design of new efficient privacy-preserving computations based on the secure multi-party computation (SMC) paradigm. In addition, by a trivial conversion of this Monte Carlo algorithm to its Las Vegas equivalent, one gets the first version of Shellsort with a running time that is provably O ( n log n ) with very high probability.

Authors

• Michael T. Goodrich

Keywords

No keywords are indexed for this paper.