### Randomized Shellsort: A Simple Data-Oblivious Sorting AlgorithmRandomized Shellsort: A Simple Data-Oblivious Sorting Algorithm

Access Restriction
Subscribed

 Author Goodrich, Michael T Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2011 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Chernoff bounds ♦ Sorting ♦ Data-oblivious algorithms 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 $\textit{O}(\textit{n}$ log $\textit{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 $\textit{O}(\textit{n}$ log $\textit{n})$ with very high probability. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2011-12-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 58 Issue Number 6 Page Count 26 Starting Page 1 Ending Page 26

#### Open content in new tab

Source: ACM Digital Library