{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T06:14:08Z","timestamp":1648620848805},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,10,25]],"date-time":"2012-10-25T00:00:00Z","timestamp":1351123200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00453-012-9696-5","type":"journal-article","created":{"date-parts":[[2012,10,24]],"date-time":"2012-10-24T14:50:52Z","timestamp":1351090252000},"page":"835-858","source":"Crossref","is-referenced-by-count":3,"title":["Spin-the-Bottle Sort and Annealing Sort: Oblivious Sorting via Round-Robin Random Comparisons"],"prefix":"10.1007","volume":"68","author":[{"given":"Michael T.","family":"Goodrich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,10,25]]},"reference":[{"key":"9696_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Sorting in clogn parallel steps. Combinatorica 3, 1\u201319 (1983)","journal-title":"Combinatorica"},{"issue":"4","key":"9696_CR2","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/0404042","volume":"4","author":"S. Assaf","year":"1991","unstructured":"Assaf, S., Upfal, E.: Fault tolerant sorting networks. SIAM J. Discrete Math. 4(4), 472\u2013480 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"9696_CR3","first-page":"307","volume-title":"Proc. 1968 Spring Joint Computer Conf.","author":"K.E. Batcher","year":"1968","unstructured":"Batcher, K.E.: Sorting networks and their applications. In: Proc. 1968 Spring Joint Computer Conf., pp.\u00a0307\u2013314. AFIPS Press, Reston (1968)"},{"key":"9696_CR4","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1145\/1455770.1455804","volume-title":"CCS\u201908: Proceedings of the 15th ACM Conference on Computer and Communications Security","author":"A. Ben-David","year":"2008","unstructured":"Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: a system for secure multi-party computation. In: CCS\u201908: Proceedings of the 15th ACM Conference on Computer and Communications Security, pp.\u00a0257\u2013266. ACM, New York (2008)"},{"issue":"3","key":"9696_CR5","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.dam.2004.01.003","volume":"144","author":"T. Biedl","year":"2004","unstructured":"Biedl, T., Chan, T., Demaine, E.D., Fleischer, R., Golin, M., King, J.A., Munro, J.I.: Fun-sort\u2014or the chaos of unordered binary search. Discrete Appl. Math. 144(3), 231\u2013236 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9696_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1109\/ICPP.1993.164","volume-title":"ICPP\u201993: Proceedings of the 1993 International Conference on Parallel Processing","author":"D.T. Blackston","year":"1993","unstructured":"Blackston, D.T., Ranade, A.: Snakesort: a family of simple optimal randomized sorting algorithms. In: ICPP\u201993: Proceedings of the 1993 International Conference on Parallel Processing, pp.\u00a0201\u2013204. IEEE Comput. Soc., Washington (1993)"},{"issue":"1","key":"9696_CR7","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1080\/15326349708807412","volume":"13","author":"A. Boneh","year":"1997","unstructured":"Boneh, A., Hofri, M.: The coupon-collector problem revisited\u2014a survey of engineering problems and computational methods. Commun. Stat., Stoch. Models 13(1), 39\u201366 (1997)","journal-title":"Commun. Stat., Stoch. Models"},{"key":"9696_CR8","first-page":"268","volume-title":"SODA\u201908: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms","author":"M. Braverman","year":"2008","unstructured":"Braverman, M., Mossel, E.: Noisy sorting without resampling. In: SODA\u201908: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0268\u2013276. SIAM, Philadelphia (2008)"},{"issue":"5","key":"9696_CR9","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0020-0190(00)00223-4","volume":"79","author":"B. Brejov\u00e1","year":"2001","unstructured":"Brejov\u00e1, B.: Analyzing variants of Shellsort. Inf. Process. Lett. 79(5), 223\u2013227 (2001)","journal-title":"Inf. Process. Lett."},{"key":"9696_CR10","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1145\/509907.509980","volume-title":"STOC\u201902: Proceedings of the Thiry Fourth Annual ACM Symposium on Theory of Computing","author":"R. Canetti","year":"2002","unstructured":"Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC\u201902: Proceedings of the Thiry Fourth Annual ACM Symposium on Theory of Computing, pp.\u00a0494\u2013503. ACM, New York (2002)"},{"key":"9696_CR11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"issue":"1","key":"9696_CR12","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1137\/0222006","volume":"22","author":"R. Cypher","year":"1993","unstructured":"Cypher, R.: A lower bound on the size of Shellsort sorting networks. SIAM J. Comput. 22(1), 62\u201371 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9696_CR13","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(80)90022-8","volume":"11","author":"W. Dobosiewicz","year":"1980","unstructured":"Dobosiewicz, W.: An efficient variation of bubble sort. Inf. Process. Lett. 11(1), 5\u20136 (1980)","journal-title":"Inf. Process. Lett."},{"key":"9696_CR14","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/508171.508174","volume-title":"NSPW\u201901: Proceedings of the 2001 Workshop on New Security Paradigms","author":"W. Du","year":"2001","unstructured":"Du, W., Atallah, M.J.: Secure multi-party computation problems and their applications: a review and open problems. In: NSPW\u201901: Proceedings of the 2001 Workshop on New Security Paradigms, pp.\u00a013\u201322. ACM, New York (2001)"},{"key":"9696_CR15","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1145\/844102.844125","volume-title":"NSPW\u201902: Proceedings of the 2002 Workshop on New Security Paradigms","author":"W. Du","year":"2002","unstructured":"Du, W., Zhan, Z.: A practical approach to solve secure multi-party computation problems. In: NSPW\u201902: Proceedings of the 2002 Workshop on New Security Paradigms, pp.\u00a0127\u2013135. ACM, New York (2002)"},{"issue":"5","key":"9696_CR16","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U. Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"key":"9696_CR17","first-page":"1","volume-title":"Symposium on Discrete Algorithms (SODA)","author":"M.T. Goodrich","year":"2010","unstructured":"Goodrich, M.T.: Randomized Shellsort: a simple oblivious sorting algorithm. In: Symposium on Discrete Algorithms (SODA), pp.\u00a01\u201316 (2010)"},{"key":"9696_CR18","volume-title":"Algorithm Design: Foundations, Analysis, and Internet Examples","author":"M.T. Goodrich","year":"2002","unstructured":"Goodrich, M.T., Tamassia, R.: Algorithm Design: Foundations, Analysis, and Internet Examples. Wiley, New York (2002)"},{"key":"9696_CR19","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-540-72914-3_17","volume-title":"FUN\u201907: Proceedings of the 4th International Conference on Fun with Algorithms","author":"H. Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M., Ruepp, O.: Sorting the slow way: an analysis of perversely awful randomized sorting algorithms. In: FUN\u201907: Proceedings of the 4th International Conference on Fun with Algorithms, pp.\u00a0183\u2013197. Springer, Berlin (2007)"},{"issue":"1","key":"9696_CR20","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"C.A.R. Hoare","year":"1962","unstructured":"Hoare, C.A.R.: Quicksort. Comput. J. 5(1), 10\u201315 (1962)","journal-title":"Comput. J."},{"issue":"2","key":"9696_CR21","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/0022-0000(85)90042-X","volume":"31","author":"J. Incerpi","year":"1985","unstructured":"Incerpi, J., Sedgewick, R.: Improved upper bounds on Shellsort. J. Comput. Syst. Sci. 31(2), 210\u2013224 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9696_CR22","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(87)90034-2","volume":"26","author":"J. Incerpi","year":"1987","unstructured":"Incerpi, J., Sedgewick, R.: Practical variations of Shellsort. Inf. Process. Lett. 26(1), 37\u201343 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"9696_CR23","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1145\/355483.355488","volume":"47","author":"T. Jiang","year":"2000","unstructured":"Jiang, T., Li, M., Vit\u00e1nyi, P.: A lower bound on the average-case complexity of Shellsort. J. ACM 47(5), 905\u2013911 (2000)","journal-title":"J. ACM"},{"key":"9696_CR24","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol. 3. Addison-Wesley, Reading (1973)"},{"key":"9696_CR25","volume-title":"Simulated Annealing: Theory and Applications","year":"1987","unstructured":"Laarhoven, P.J.M., Aarts, E.H.L. (eds.): Simulated Annealing: Theory and Applications. Kluwer Academic, Norwell (1987)"},{"key":"9696_CR26","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F.T. Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo (1992)"},{"issue":"1","key":"9696_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539794268406","volume":"27","author":"T. Leighton","year":"1998","unstructured":"Leighton, T., Plaxton, C.G.: Hypercubic sorting networks. SIAM J. Comput. 27(1), 1\u201347 (1998)","journal-title":"SIAM J. Comput."},{"key":"9696_CR28","first-page":"20","volume-title":"SSYM\u201904: Proceedings of the 13th Conference on USENIX Security Symposium","author":"D. Malkhi","year":"2004","unstructured":"Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay\u2014a secure two-party computation system. In: SSYM\u201904: Proceedings of the 13th Conference on USENIX Security Symposium, p.\u00a020. USENIX Association, Berkeley (2004)"},{"issue":"2","key":"9696_CR29","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1016\/j.dam.2005.03.020","volume":"154","author":"U. Maurer","year":"2006","unstructured":"Maurer, U.: Secure multi-party computation made simple. Discrete Appl. Math. 154(2), 370\u2013381 (2006)","journal-title":"Discrete Appl. Math."},{"key":"9696_CR30","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)"},{"key":"9696_CR31","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"issue":"1","key":"9696_CR32","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF01840378","volume":"5","author":"M. Paterson","year":"1990","unstructured":"Paterson, M.: Improved sorting networks with O(logN) depth. Algorithmica 5(1), 75\u201392 (1990)","journal-title":"Algorithmica"},{"issue":"2","key":"9696_CR33","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jagm.1996.0825","volume":"23","author":"C.G. Plaxton","year":"1997","unstructured":"Plaxton, C.G., Suel, T.: Lower bounds for Shellsort. J. Algorithms 23(2), 221\u2013240 (1997)","journal-title":"J. Algorithms"},{"key":"9696_CR34","unstructured":"Pratt, V.R.: Shellsort and sorting networks. Ph.D. Thesis, Stanford University, Stanford, CA, USA (1972)"},{"key":"9696_CR35","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1109\/IPDPS.2005.334","volume-title":"IPDPS\u201905: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201905)\u2014Papers","author":"S. Rajasekaran","year":"2005","unstructured":"Rajasekaran, S., Sen, S.: PDM sorting algorithms that take a small number of passes. In: IPDPS\u201905: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201905)\u2014Papers, p.\u00a010. IEEE Comput. Soc., Washington (2005)"},{"key":"9696_CR36","volume-title":"Algorithms in C++","author":"R. Sedgewick","year":"1992","unstructured":"Sedgewick, R.: Algorithms in C++. Addison-Wesley, Reading (1992)"},{"key":"9696_CR37","first-page":"1","volume-title":"ESA\u201996: Proceedings of the Fourth Annual European Symposium on Algorithms","author":"R. Sedgewick","year":"1996","unstructured":"Sedgewick, R.: Analysis of Shellsort and related algorithms. In: ESA\u201996: Proceedings of the Fourth Annual European Symposium on Algorithms, pp.\u00a01\u201311. Springer, London (1996)"},{"issue":"3","key":"9696_CR38","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/s00453-007-9025-6","volume":"53","author":"J. Seiferas","year":"2009","unstructured":"Seiferas, J.: Sorting networks of logarithmic depth, further simplified. Algorithmica 53(3), 374\u2013384 (2009)","journal-title":"Algorithmica"},{"issue":"7","key":"9696_CR39","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/368370.368387","volume":"2","author":"D.L. Shell","year":"1959","unstructured":"Shell, D.L.: A high-speed sorting procedure. Commun. ACM 2(7), 30\u201332 (1959)","journal-title":"Commun. ACM"},{"key":"9696_CR40","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1145\/1755688.1755716","volume-title":"5th ACM Symposium on Information, Computer and Communications Security (ASIACCS)","author":"G. Wang","year":"2010","unstructured":"Wang, G., Luo, T., Goodrich, M.T., Du, W., Zhu, Z.: Bureaucratic protocols for secure two-party sorting, selection, and permuting. In: 5th ACM Symposium on Information, Computer and Communications Security (ASIACCS), pp.\u00a0226\u2013237. ACM, New York (2010)"},{"issue":"3","key":"9696_CR41","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(88)90158-5","volume":"28","author":"M.A. Weiss","year":"1988","unstructured":"Weiss, M.A., Sedgewick, R.: Bad cases for shaker-sort. Inf. Process. Lett. 28(3), 133\u2013136 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9696_CR42","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. Williams","year":"1964","unstructured":"Williams, J.: Algorithm 232: Heasort. Commun. ACM 7, 347\u2013348 (1964)","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9696-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9696-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9696-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T13:57:17Z","timestamp":1643551037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9696-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,25]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9696"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9696-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,25]]}}}