{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T23:14:18Z","timestamp":1763507658563,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-08-1-1015"],"award-info":[{"award-number":["N00014-08-1-1015"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["7.25E+40"],"award-info":[{"award-number":["7.25E+40"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>\n            In this article, we describe a\n            <jats:italic>randomized Shellsort<\/jats:italic>\n            algorithm. This algorithm is a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) with very high probability.\n          <\/jats:p>","DOI":"10.1145\/2049697.2049701","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T15:45:47Z","timestamp":1323791147000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Randomized Shellsort"],"prefix":"10.1145","volume":"58","author":[{"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[{"name":"University of California, Irvine"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579338"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100232"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404042"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90075-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.53587"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455804"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.1993.164"},{"volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Braverman M.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00223-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509980"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_2_1_12_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press Cambridge MA. Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press Cambridge MA."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222006"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90022-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/508171.508174"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/844102.844125"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"volume-title":"Proceedings of the European Symposium on Algorithms (ESA). 194--205","author":"Franceschini G.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226670"},{"volume-title":"Algorithm Design: Foundations, Analysis, and Internet Examples","year":"2002","author":"Goodrich M. T.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding W.","year":"1963","journal-title":"J. AMS Statistical Association"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90042-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90034-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/355483.355488"},{"key":"e_1_2_1_26_1","volume-title":"The Art of Computer Programming","volume":"3","author":"Knuth D. E.","year":"1973"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Leighton F. T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes. Morgan-Kaufmann San Francisco CA. Leighton F. T. 1992. Introduction to Parallel Algorithms and Architectures: Arrays Trees Hypercubes . Morgan-Kaufmann San Francisco CA.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.5009385"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268406"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010049"},{"volume-title":"Proceedings of the 13th Conference on USENIX Security Symposium (SSYM\u201904)","author":"Malkhi D.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.03.020"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"McGeoch C. Sanders P. Fleischer R. Cohen P. R. and Precup D. 2002. Using finite experiments to study asymptotic performance. In Experimental algorithmics: From Algorithm Design to Robust and Efficient Software. Springer-Verlag Berlin Germany 93--126. McGeoch C. Sanders P. Fleischer R. Cohen P. R. and Precup D. 2002. Using finite experiments to study asymptotic performance. In Experimental algorithmics: From Algorithm Design to Robust and Efficient Software . Springer-Verlag Berlin Germany 93--126.","DOI":"10.1007\/3-540-36383-1_5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press Cambridge UK. Mitzenmacher M. and Upfal E. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge UK. Motwani R. and Raghavan P. 1995. Randomized Algorithms . Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840378"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0825"},{"key":"e_1_2_1_38_1","unstructured":"Pratt V. R. 1972. Shellsort and sorting networks. Ph.D. thesis Stanford University Palo Alto CA. Pratt V. R. 1972. Shellsort and sorting networks. Ph.D. thesis Stanford University Palo Alto CA."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.334"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.9"},{"volume-title":"Proceedings of the 4th International Workshop on Algorithm Engineering (WAE\u201900)","author":"Sanders P.","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.16500"},{"key":"e_1_2_1_43_1","unstructured":"Sedgewick R. 1992. Algorithms in C++. Addison-Wesley Reading MA. Sedgewick R. 1992. Algorithms in C++ . Addison-Wesley Reading MA."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/647906.739656"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9025-6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/259380.259432"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/368370.368387"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90158-5"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049701","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2049697.2049701","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:41Z","timestamp":1750278401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049701"}},"subtitle":["A Simple Data-Oblivious Sorting Algorithm"],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2049697.2049701"],"URL":"https:\/\/doi.org\/10.1145\/2049697.2049701","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2010-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}