Randomized Shellsort
Abstract
In this article, 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 multiparty 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 01, 2011
- Source ID
- 10.1145/2049697.2049701
Entities
People
- Michael T. Goodrich
Organizations
- National Science Foundation
- Office of Naval Research
- University of California, Irvine