{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:39Z","timestamp":1759638159532},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_41","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:07:12Z","timestamp":1330204032000},"page":"499-509","source":"Crossref","is-referenced-by-count":9,"title":["Heapsort\u2014Adapted for presorted files"],"prefix":"10.1007","author":[{"given":"Christos","family":"Levcopoulos","sequence":"first","affiliation":[]},{"given":"Ola","family":"Petersson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"issue":"11","key":"41_CR1","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1145\/359024.359026","volume":"23","author":"C. R. Cook","year":"1980","unstructured":"C.R Cook and D.J. Kim. Best sorting algorithms for nearly sorted lists. Communications of the ACM, 23(11):620\u2013624, 1980.","journal-title":"Communications of the ACM"},{"key":"41_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin\/Heidelberg, F.R. Germany, 1987."},{"key":"41_CR3","series-title":"Research Report","volume-title":"A new measure of presortedness","author":"V. Estivill-Castro","year":"1987","unstructured":"V. Estivill-Castro and D. Wood. A new measure of presortedness. Research Report CS-87-58, University of Waterloo, Department of Computer Science, Waterloo, Canada, 1987."},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"L.J. Guibas, E.M. McCreight, M.F. Plass, and J.R. Roberts. A new representation of linear lists. In Proc. 9th Annual ACM Symposium on Theory of Computing, pages 49\u201360, 1977.","DOI":"10.1145\/800105.803395"},{"key":"41_CR5","series-title":"Technical Report","volume-title":"Implementation of a sorting algorithm suitable for presorted files","author":"H Mannila","year":"1984","unstructured":"H Mannila. Implementation of a sorting algorithm suitable for presorted files. Technical Report, Department of Computer Science, University of Helsinki, Finland, 1984."},{"issue":"4","key":"41_CR6","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"C-34","author":"H. Mannila","year":"1985","unstructured":"H. Mannila. Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers, C-34(4):318\u2013325, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Sorting presorted files. In Proc. 4th GI Conference on Theoretical Computer Science, pages 199\u2013212, Springer-Verlag, 1979.","DOI":"10.1007\/3-540-09118-1_22"},{"key":"41_CR8","volume-title":"Data Structures and Algorithms, Vol 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms, Vol 1: Sorting and Searching. Springer-Verlag, Berlin\/Heidelberg, F.R. Germany, 1984."},{"key":"41_CR9","volume-title":"Data Structures and Algorithms, Vol. 3: Multidimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms, Vol. 3: Multidimensional Searching and Computational Geometry. Springer-Verlag, Berlin\/Heidelberg, F.R. Germany, 1984."},{"key":"41_CR10","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O'Rourke","year":"1987","unstructured":"J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, New York\/Oxford, 1987."},{"key":"41_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, N.Y., 1985."},{"key":"41_CR12","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1007\/BF01954897","volume":"28","author":"S. S. Skiena","year":"1988","unstructured":"S.S. Skiena. Encroaching lists as a measure of presortedness. BIT, 28:775\u2013784, 1988.","journal-title":"BIT"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:04:40Z","timestamp":1619571880000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}