{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T16:13:43Z","timestamp":1781194423692,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540616801","type":"print"},{"value":"9783540706670","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61680-2_42","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:10:19Z","timestamp":1330294219000},"page":"1-11","source":"Crossref","is-referenced-by-count":10,"title":["Analysis of Shellsort and related algorithms"],"prefix":"10.1007","author":[{"given":"Robert","family":"Sedgewick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szem\u00e9rdi.\u201cAn O(n log n) sorting network\u201d, in Troc. I5th Ann. ACM Symp. on Theory of Computing, 1983.","DOI":"10.1145\/800061.808726"},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szem\u00e9rdi. \u201cSorting in clog n parallel steps\u201d, Combinatorica 3, 1983, 1\u201319.","journal-title":"Combinatorica"},{"key":"1_CR3","first-page":"307","volume":"32","author":"K. Batcher","year":"1968","unstructured":"K. Batcher. Sorting networks and their applications in Proceedings of the AFIPS Spring Joint Computer Conference 32, 1968, 307\u2013314.","journal-title":"Proceedings of the AFIPS Spring Joint Computer Conference"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"299","DOI":"10.2307\/2371684","volume":"64","author":"A. Brauer","year":"1942","unstructured":"A. Brauer. \u201cOn a problem of partitiions\u201d, Amer. J. Math. 64, 1942, 299\u2013312.","journal-title":"Amer. J. Math."},{"key":"1_CR5","volume-title":"Solution to Problem 7382 (Mathematics)","author":"W. Curran-Sharp","year":"1884","unstructured":"W. Curran-Sharp. \u201cSolution to Problem 7382 (Mathematics)\u201d, Ed. times (London) 1, 1884."},{"key":"1_CR6","unstructured":"B. Chazelle. Private communication, 1983."},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1137\/0222006","volume":"22","author":"R. Cypher","year":"1993","unstructured":"R. Cypher.\u201cA lower bound on the size of Shellsort sorting networks\u201d, SIAM J. Computing 22, 1993, 62\u201371.","journal-title":"SIAM J. Computing"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(80)90022-8","volume":"11","author":"W. Dobosiewicz","year":"1980","unstructured":"W. Dobosiewicz.\u201cAn efficient variation of bubble sort\u201d. Information Processing Letters 11, 1980, 5\u20136.","journal-title":"Information Processing Letters"},{"key":"1_CR9","volume-title":"Handbook of Algorithms and Data Structures","author":"G. Gonnet","year":"1991","unstructured":"G. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures, 2nd edition, Addison-Wesley, Reading, MA, 1991.","edition":"2nd edition"},{"key":"1_CR10","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF01403673","volume":"34","author":"H. Greenberg","year":"1980","unstructured":"H. Greenberg. \u201cAn algorithm for a linear diophantine equation and a problem of Frobenius\u201d, Numer. Math. 34, 1980, 349\u2013352.","journal-title":"Numer. Math."},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1145\/366552.366557","volume":"6","author":"T. Hibbard","year":"1963","unstructured":"T. Hibbard. \u201cAn empirical study of minimal storage sorting\u201d, Communications of the ACM 6, 1963, 206\u2013213.","journal-title":"Communications of the ACM"},{"key":"1_CR12","first-page":"1","volume":"5","author":"G. Hofmeister","year":"1966","unstructured":"G. Hofmeister. \u201cZu einem Problem von Frobenius\u201d, Norske Vid. Selsk. Skr. 5, 1966, 1\u201337.","journal-title":"Norske Vid. Selsk. Skr."},{"key":"1_CR13","unstructured":"J. Incerpi. A Study of the Worst Case of Shellsort, Ph.D. thesis, Brown University, Department of Computer Science, 1985."},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/0022-0000(85)90042-X","volume":"31","author":"J. Incerpi","year":"1985","unstructured":"J. Incerpi and R. Sedgewick. \u201cImproved Upper Bounds on Shellsort\u201d, J. of Computer and System Sciences 31, 1985, 210\u2013224.","journal-title":"J. of Computer and System Sciences"},{"key":"1_CR15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(87)90034-2","volume":"26","author":"J. Incerpi","year":"1987","unstructured":"J. Incerpi and R. Sedgewick. \u201cPractical variations of Shellsort\u201d, Information Processing Letters 26, 1987, 37\u201343.","journal-title":"Information Processing Letters"},{"key":"1_CR16","doi-asserted-by":"crossref","first-page":"390","DOI":"10.4153\/CJM-1960-033-6","volume":"12","author":"S. Johnson","year":"1960","unstructured":"S. Johnson. \u201cA linear diophantine problem\u201d, Canad. J. Math. 12, 1960, 390\u2013398.","journal-title":"Canad. J. Math."},{"key":"1_CR17","volume-title":"The Art of Computer Programming. Volume 3: Sorting and Searching","author":"D. Knuth","year":"1973","unstructured":"D. Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973."},{"key":"1_CR18","unstructured":"D. Knuth. Private communication, 1995."},{"key":"1_CR19","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/366947.366957","volume":"3","author":"R. Lazarus","year":"1960","unstructured":"R. Lazarus and R. Frank. \u201cA high-speed sorting procedure\u201d, Communications of the ACM 3, 1960, 20\u201322.","journal-title":"Communications of the ACM"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"T. Leighton. \u201cTight bounds on the complexity of parallel sorting\u201d, in Proc. 16th Ann. ACM Symp. on Theory of Computing, 1984.","DOI":"10.1145\/800057.808667"},{"key":"1_CR21","first-page":"672","volume-title":"Introduction to parallel algorithms and architectures","author":"T. Leighton","year":"1992","unstructured":"T. Leighton. Introduction to parallel algorithms and architectures, Morgan Kaufmann, San Mateo, CA, 1992, 672."},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"T. Leighton and G. Plaxton. \u201cA (fairly) simple circuit that (usually) sorts\u201d, in Proc. 31st IEEE Symposium on Foundations of Computer Science, 1990, 264\u2013274.","DOI":"10.1109\/FSCS.1990.89545"},{"key":"1_CR23","volume-title":"SCAMP working paper no. P18\/94","author":"P. Lemke","year":"1994","unstructured":"P. Lemke. \u201cThe performance of randomized Shellsort-like network sorting algorithms\u201d, SCAMP working paper no. P18\/94, Institute for Defense Analyses, Princeton, NJ, 1994."},{"key":"1_CR24","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1112\/blms\/5.1.75","volume":"5","author":"M. Lewin","year":"1973","unstructured":"M. Lewin. \u201cOn a linear diophantine problem\u201d, Bull. London Math. Soc. 5, 1973, 75\u201378.","journal-title":"Bull. London Math. Soc."},{"key":"1_CR25","first-page":"63","volume":"1","author":"A. Papernov","year":"1965","unstructured":"A. Papernov and G. Stasevich. \u201cA method of information sorting in computer memories\u201d, Problems of Information Transmission 1, 1965, 63\u201375.","journal-title":"Problems of Information Transmission"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"C. Plaxton and T. Suel. \u201cImproved lower bounds for Shellsort\u201d, J. of Algorithms, to appear. Preliminary version in Proc. 33nd IEEE Symposium on Foundations of Computer Science, 1992, 226\u2013235.","DOI":"10.1109\/SFCS.1992.267769"},{"key":"1_CR27","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1006\/jagm.1993.1032","volume":"15","author":"B. Poonen","year":"1993","unstructured":"B. Poonen. \u201cThe worst case in Shellsort and related algorithms\u201d, J. of Algorithms 15, 1993, 101\u2013124.","journal-title":"J. of Algorithms"},{"key":"1_CR28","unstructured":"V. Pratt. Shellsort and Sorting Networks, Garland, New York, 1979; Ph.D. thesis, Stanford University, 1971."},{"key":"1_CR29","volume-title":"SCAMP working paper no. 22\/89","author":"D. Robbins","year":"1989","unstructured":"D. Robbins. \u201cExperiments with shaker sort on the CRAY-2\u201d, SCAMP working paper no. 22\/89, Institute for Defense Analyses, Princeton, NJ, 1989."},{"key":"1_CR30","volume-title":"Algorithms","author":"R. Sedgewick","year":"1988","unstructured":"R. Sedgewick. Algorithms, 2nd edition, Addison-Wesley, Reading, Mass, 1988.","edition":"2nd edition"},{"key":"1_CR31","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0196-6774(86)90001-5","volume":"7","author":"R. Sedgewick","year":"1986","unstructured":"R. Sedgewick. \u201cA new upper bound for Shellsort\u201d, J. Algorithms 7, 1986, 159\u2013173.","journal-title":"J. Algorithms"},{"key":"1_CR32","unstructured":"R. Sedgewick. \u201cBricksort networks\u201d, in preparation."},{"key":"1_CR33","volume-title":"An Introduction to the Analysis of Algorithms","author":"R. Sedgewick","year":"1996","unstructured":"R. Sedgewick and P, Flajolet. An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, Mass., 1996."},{"key":"1_CR34","first-page":"1","volume":"294","author":"E. Selmer","year":"1977","unstructured":"E. Selmer. \u201cOn the linear diophantine problem of Frobenius\u201d, J. Reine Angew. Math. 294, 1977, 1\u201317.","journal-title":"J. Reine Angew. Math."},{"key":"1_CR35","volume-title":"TR 87-27","author":"E. Selmer","year":"1987","unstructured":"E. Selmer. \u201cOn Shellsort and the Frobenius problem\u201d, TR 87-27, Department of Mathematics, University of Bergen, Norway, 1987."},{"key":"1_CR36","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/368370.368387","volume":"2","author":"D. Shell","year":"1959","unstructured":"D. Shell. \u201cA high-speed sorting procedure\u201d, Communications of the ACM 2, 1959, 30\u201332.","journal-title":"Communications of the ACM"},{"key":"1_CR37","first-page":"431","volume-title":"Handbook of Theoretical Computer Science A: Algorithms and Complexity","author":"J. Vitter","year":"1990","unstructured":"J. Vitter and P. Flajolet, \u201cAnalysis of algorithms and data structures\u201d, in Handbook of Theoretical Computer Science A: Algorithms and Complexity, J. van Leeuwen, ed., Elsevier, Amsterdam, 1990, 431\u2013524."},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"M. Weiss. Lower Bounds for Shellsort, Ph.D. thesis, Princeton University, Department of Computer Science, June 1987.","DOI":"10.1007\/3-540-19487-8_29"},{"key":"1_CR39","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1093\/comjnl\/34.1.88","volume":"34","author":"M. Weiss","year":"1991","unstructured":"M. Weiss. \u201cEmpirical study of the expected running time of Shellsort\u201d, Computer Journal 34, 1991, 88\u201391.","journal-title":"Computer Journal"},{"key":"1_CR40","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(88)90158-5","volume":"28","author":"M. Weiss","year":"1988","unstructured":"M. Weiss and R. Sedgewick. \u201cBad cases for shakersort\u201d, Information Processing Letters 28, 1988, 133\u2013136.","journal-title":"Information Processing Letters"},{"key":"1_CR41","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/0196-6774(90)90005-Y","volume":"11","author":"M. Weiss","year":"1990","unstructured":"M. Weiss and R. Sedgewick. \u201cTight lower bounds for Shellsort\u201d, J. of Algorithms 11, 1990, 242\u2013251.","journal-title":"J. of Algorithms"},{"key":"1_CR42","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0020-0190(90)90134-J","volume":"34","author":"M. Weiss","year":"1990","unstructured":"M. Weiss and R. Sedgewick. \u201cMore on Shellsort increment sequences\u201d, Information Processing Letters 34, 1990, 267\u2013270.","journal-title":"Information Processing Letters"},{"key":"1_CR43","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0196-6774(80)90003-6","volume":"1","author":"A. Yao","year":"1980","unstructured":"A. Yao. \u201cAn analysis of (h, k, 1) Shellsort\u201d, Journal of Algorithms 1, 1980, 14\u201350.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61680-2_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T19:15:47Z","timestamp":1687288547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61680-2_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616801","9783540706670"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/3-540-61680-2_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}