{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:11Z","timestamp":1725488531360},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_21","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"254-266","source":"Crossref","is-referenced-by-count":13,"title":["On the Performance of WEAK-HEAPSORT"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ingo","family":"Wegener","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"21_CR1","first-page":"32816","volume-title":"The weak-heap data structure","author":"R. D. Dutton","year":"1992","unstructured":"R. D. Dutton. The weak-heap data structure. Technical report, University of Central Florida, Orlando, FL 32816, 1992."},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/BF01990520","volume":"33","author":"R. D. Dutton","year":"1993","unstructured":"R. D. Dutton. Weak-heap sort. BIT, 33:372\u2013381, 1993.","journal-title":"BIT"},{"key":"21_CR3","unstructured":"S. Edelkamp and I. Wegener. On the performance of WEAK-HEAPSORT. Technical Report TR99-028, Electronic Colloquium on Computational Complexity, 1999. ISSN 1433-8092, 6th Year."},{"issue":"2","key":"21_CR4","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/BF01182770","volume":"11","author":"R. Fleischer","year":"1994","unstructured":"R. Fleischer. A tight lower bound for the worst case of Bottom-Up-Heapsort. Algorithmica, 11(2):104\u2013115, 1994.","journal-title":"Algorithmica"},{"issue":"12","key":"21_CR5","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R. W. Floyd","year":"1964","unstructured":"R. W. Floyd. ACM algorithm 245: Treesort 3. Communications of the ACM, 7(12):701, 1964.","journal-title":"Communications of the ACM"},{"issue":"5","key":"21_CR6","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/366552.366557","volume":"6","author":"T. N. Hibbard","year":"1963","unstructured":"T. N. Hibbard. A empirical study of minimal storage sorting. Communications of the ACM, 6(5):206\u2013213, 1963.","journal-title":"Communications of the ACM"},{"issue":"1","key":"21_CR7","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"C. A. R. Hoare","year":"1962","unstructured":"C. A. R. Hoare. Quicksort. Computer Journal, 5(1):10\u201315, 1962.","journal-title":"Computer Journal"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/0022-0000(85)90042-X","volume":"31","author":"J. Incerpi","year":"1985","unstructured":"J. Incerpi and R. Sedgewick. Improved upper bounds on shellsort. Journal of Computer and System Sciences, 31:210\u2013224, 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/3-540-48523-6_42","volume-title":"ICALP\u201999","author":"T. Jiang","year":"1999","unstructured":"T. Jiang, M. Li, and P. Vit\u00e1nyi. Average complexity of shellsort. In ICALP\u201999, volume 1644 of LNCS, pages 453\u2013462, 1999."},{"issue":"3","key":"21_CR10","first-page":"87","volume":"20","author":"J. Katajainen","year":"1998","unstructured":"J. Katajainen. The ultimate heapsort. In Proceedings of the Computing: the 4th Australasian Theory Symposium, Australian Computer Science Communications 20(3), pages 87\u201395, 1998.","journal-title":"Proceedings of the Computing: the 4th Australasian Theory Symposium, Australian Computer Science Communications"},{"issue":"1","key":"21_CR11","first-page":"27","volume":"3","author":"J. Katajainen","year":"1996","unstructured":"J. Katajainen, T. Pasanen, and J. Teuhola. Practical in-place mergesort. Nordic Journal of Computing, 3(1):27\u201340, 1996.","journal-title":"Nordic Journal of Computing"},{"issue":"1","key":"21_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0020-0190(99)00038-1","volume":"70","author":"J. Katajainen","year":"1999","unstructured":"J. Katajainen and T. A. Pasanen. In-place sorting with fewer moves. Information Processing Letters, 70(1):31\u201337, 1999.","journal-title":"Information Processing Letters"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"M. Li and P. Vit\u00e1nyi. An Introduction to Kolmogorov Complexity and Its Applications. Text and Monographs in Computer Science. Springer-Verlag, 1993.","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/0196-6774(89)90033-3","volume":"10","author":"C. J. H. McDiarmid","year":"1989","unstructured":"C. J. H. McDiarmid and B. A. Reed. Building heaps fast. Journal of Algorithms, 10:352\u2013365, 1989.","journal-title":"Journal of Algorithms"},{"key":"21_CR15","unstructured":"S. Nilsson. Radix Sorting & Searching. PhD thesis, Lund University, 1996."},{"issue":"3","key":"21_CR16","first-page":"63","volume":"1","author":"A. Papernov","year":"1965","unstructured":"A. Papernov and G. Stasevich. The worst case in shellsort and related algorithms. Problems Inform. Transmission, 1(3):63\u201375, 1965.","journal-title":"Problems Inform. Transmission"},{"key":"21_CR17","unstructured":"V. Pratt. Shellsort and Sorting Networks. PhD thesis, Stanford University, 1979."},{"key":"21_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/3-540-56279-6_101","volume-title":"Sorting in-place with a worst case complexity of n log n \u2014 1.3n + O(log n) comparisons and \u03b5n log n+ O(1) transports","author":"K. Reinhardt","year":"1992","unstructured":"K. Reinhardt. Sorting in-place with a worst case complexity of n log n \u2014 1.3n + O(log n) comparisons and \u03b5n log n+ O(1) transports. Lecture Notes in Computer Science, 650:489\u2013499, 1992."},{"key":"21_CR19","unstructured":"W. Rudin. Real and Complex Analysis. McGraw-Hill, 1974."},{"issue":"1","key":"21_CR20","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1006\/jagm.1993.1031","volume":"15","author":"R. Schaffer","year":"1993","unstructured":"R. Schaffer and R. Sedgewick. The analysis of heapsort. Journal of Algorithms, 15(1):76\u2013100, 1993.","journal-title":"Journal of Algorithms"},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF00289467","volume":"7","author":"R. Sedgewick","year":"1977","unstructured":"R. Sedgewick. The analysis of quicksort programs. Acta Inform., 7:327\u2013355, 1977.","journal-title":"Acta Inform."},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0196-6774(86)90001-5","volume":"2","author":"R. Sedgewick","year":"1986","unstructured":"R. Sedgewick. A new upper bound for shellsort. Journal of Algorithms, 2:159\u2013173, 1986.","journal-title":"Journal of Algorithms"},{"issue":"7","key":"21_CR23","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/368370.368387","volume":"2","author":"D. Shell","year":"1959","unstructured":"D. Shell. A high-speed sorting procedure. Communications of the ACM, 2(7):30\u201332, 1959.","journal-title":"Communications of the ACM"},{"key":"21_CR24","volume-title":"One hundred problems in elemantary mathematics (Problems 52,85)","author":"H. Steinhaus","year":"1958","unstructured":"H. Steinhaus. One hundred problems in elemantary mathematics (Problems 52,85). Pergamon Press, London, 1958."},{"key":"21_CR25","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1145\/362736.362753","volume":"13","author":"M. H. Emden van","year":"1970","unstructured":"M. H. van Emden. Increasing the efficiency of QUICKSORT. Communications of the ACM, 13:563\u2013567, 1970.","journal-title":"Communications of the ACM"},{"issue":"1","key":"21_CR26","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0890-5401(92)90005-Z","volume":"97","author":"I. Wegener","year":"1992","unstructured":"I. Wegener. The worst case complexity of McDiarmid and Reed\u2019s variant of BOTTOM-UP HEAPSORT is less than n log n+1.1n. Information and Computation, 97(1):86\u201396, 1992.","journal-title":"Information and Computation"},{"key":"21_CR27","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0304-3975(93)90364-Y","volume":"118","author":"I. Wegener","year":"1993","unstructured":"I. Wegener. BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT, beating, on an average, QUICKSORT (if n is not very small). Theoretical Computer Science, 118:81\u201398, 1993.","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"21_CR28","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. W. J. Williams","year":"1964","unstructured":"J. W. J. Williams. ACM algorithm 232: Heapsort. Communications of the ACM, 7(6):347\u2013348, 1964.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,21]],"date-time":"2021-08-21T03:15:18Z","timestamp":1629515718000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}