{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:58:00Z","timestamp":1725663480618},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540518594"},{"type":"electronic","value":"9783540468318"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51859-2_19","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:18:36Z","timestamp":1330204716000},"page":"239-253","source":"Crossref","is-referenced-by-count":3,"title":["Local insertion sort revisited"],"prefix":"10.1007","author":[{"given":"Jyrki","family":"Katajainen","sequence":"first","affiliation":[]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[]},{"given":"Ola","family":"Petersson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"19_CR1","unstructured":"T. Altman and Y. Igarashi. Roughly sorting, sequential and parallel approach. Technical Report CS-88-7, Gunma University, Department of Computer Science, Kiryu, Japan, 1988."},{"issue":"11","key":"19_CR2","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":"19_CR3","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":"19_CR4","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":"19_CR5","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":"19_CR6","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"D.E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973."},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos and O. Petersson. An optimal parallel algorithm for sorting presorted files. In Proc. 8th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 154\u2013160, Springer-Verlag, 1988.","DOI":"10.1007\/3-540-50517-2_78"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos and O. Petersson. Heapsort\u2014adapted for presorted files. In Proc. 1989 Workshop on Algorithms and Data Structures, Springer-Verlag, 1989. To appear.","DOI":"10.1007\/3-540-51542-9_41"},{"key":"19_CR9","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":"19_CR10","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":"19_CR11","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":"19_CR12","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":"19_CR13","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":"19_CR14","series-title":"Lecture Notes in Computer Science","volume-title":"The Design of Dynamic Data Structures","author":"M.H. Overmars","year":"1983","unstructured":"M.H. Overmars. The Design of Dynamic Data Structures. Lecture Notes in Computer Science 156, Springer-Verlag, Berlin\/Heidelberg, F.R.Germany, 1983."},{"key":"19_CR15","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":"19_CR16","volume-title":"Operating System Concepts","author":"J.L. Peterson","year":"1986","unstructured":"J.L. Peterson and A. Silberschatz. Operating System Concepts. Addison Wesley, Reading, Mass., second edition, 1986.","edition":"second edition"},{"key":"19_CR17","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"},{"issue":"1","key":"19_CR18","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"R.E. Tarjan","year":"1988","unstructured":"R.E. Tarjan and C.J. Van Wyk. An O(n log log n)-time algorithm for triangulating a simple polygon. SIAM Journal on Computing, 17(1):143\u2013178, 1988.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Optimal Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51859-2_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:05:54Z","timestamp":1619571954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51859-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540518594","9783540468318"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-51859-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}