{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:22Z","timestamp":1725662902258},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540133452"},{"type":"electronic","value":"9783540388869"}],"license":[{"start":{"date-parts":[[1984,1,1]],"date-time":"1984-01-01T00:00:00Z","timestamp":441763200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1984]]},"DOI":"10.1007\/3-540-13345-3_29","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:02:22Z","timestamp":1330192942000},"page":"324-336","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Measures of presortedness and optimal sorting algorithms"],"prefix":"10.1007","author":[{"given":"Heikki","family":"Mannila","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"29_CR1","unstructured":"R. Ash: Information theory. Interscience Publishers, 1965."},{"issue":"3","key":"29_CR2","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0209045","volume":"9","author":"M. R. Brown","year":"1980","unstructured":"M.R. Brown & R.E. Tarjan: Design and analysis of a data structure for representing sorted lists. SIAM Journal on Computing 9, 3 (Aug. 1980), 594\u2013614.","journal-title":"SIAM Journal on Computing"},{"issue":"11","key":"29_CR3","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/359024.359026","volume":"23","author":"C. R. Cook","year":"1980","unstructured":"C.R. Cook & D.J. Kim: Best sorting algorithm for nearly sorted lists. Communications of the ACM 23, 11 (Nov. 1980), 620\u2013624.","journal-title":"Communications of the ACM"},{"key":"29_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00625277","volume":"18","author":"R. B. K. K. Dewar","year":"1982","unstructured":"R.B.K. Dewar, S.M. Merritt & M. Sharir: Some modified algorithms for Dijkstra's longest upsequence problem. Acta Informatica 18 (1982), 1\u201315.","journal-title":"Acta Informatica"},{"key":"29_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288531","volume":"13","author":"E. W. Dijkstra","year":"1980","unstructured":"E.W. Dijkstra: Some beautiful arguments using mathematical induction. Acta Informatica 13 (1980), 1\u201313","journal-title":"Acta Informatica"},{"key":"29_CR6","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0167-6423(82)90016-8","volume":"1","author":"E. W. Dijkstra","year":"1982","unstructured":"E.W. Dijkstra: Smoothsort, an alternative to sorting in situ. Science of Computer Programming 1 (1982), 223\u2013233.","journal-title":"Science of Computer Programming"},{"issue":"1","key":"29_CR7","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1137\/0210007","volume":"10","author":"M. H. Ellis","year":"1981","unstructured":"M.H. Ellis & J.M. Steele: Fast searching of Weyl sequences using comparisons. SIAM Journal on Computing 10, 1 (Feb. 1981), 88\u201395.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"M.L. Fredman: Two applications of a probabilistic search technique: sorting X+Y and building balanced search trees. In: Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975, p. 240\u2013244","DOI":"10.1145\/800116.803774"},{"key":"29_CR9","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M. L. Fredman","year":"1976","unstructured":"M.L. Fredman: How good is the information theory bound in sorting? Theoretical Computer Science 1 (1976), 355\u2013361.","journal-title":"Theoretical Computer Science"},{"key":"29_CR10","unstructured":"L.J. Guibas, E.M. McCreight, M.F. Plass & J.R. Roberts: A new representation of linear lists. In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977, p. 49\u201360."},{"issue":"6","key":"29_CR11","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/360825.360869","volume":"18","author":"L. H. Harper","year":"1975","unstructured":"L.H. Harper, T.H. Payne, J.E. Savage & E. Straus: Sorting X+Y. Communications of the ACM 18, 6 (June 1975), 347\u2013349.","journal-title":"Communications of the ACM"},{"key":"29_CR12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0020-0190(83)90116-3","volume":"16","author":"S. Hertel","year":"1983","unstructured":"S. Hertel: Smoothsort's behaviour on presorted sequences. Information Processing Letters 16 (1983), 165\u2013170.","journal-title":"Information Processing Letters"},{"key":"29_CR13","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston & K. Mehlhorn: A new data structure for representing sorted lists. Acta Informatica 17 (1982), 157\u2013184.","journal-title":"Acta Informatica"},{"key":"29_CR14","unstructured":"D.E. Knuth: The Art of Computer Programming, Vol. III: Sorting and Searching. Addison-Wesley, 1973."},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"S.R. Kosaraju: Localized search in sorted lists. In: Proceedings of the 11th Annual ACM Conference on Theory of Computing, 1981, p. 62\u201369.","DOI":"10.1145\/800076.802458"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"H. Mannila: Measures of presortedness and optimal sorting algorithms. Report C-1984-14, Department of Computer Science, University of Helsinki, 1984.","DOI":"10.1007\/3-540-13345-3_29"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn: Searching, sorting and information theory. In: Mathematical Foundations of Computer Science 1979, J. Becvar (ed.), Springer-Verlag, 1979, p. 131\u2013145.","DOI":"10.1007\/3-540-09526-8_10"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn: Sorting presorted files. In: 4th GI Conference on Theoretical Computer Science, Springer-Verlag, 1979, p. 199\u2013212.","DOI":"10.1007\/3-540-09118-1_22"},{"key":"29_CR19","unstructured":"R. Sedgewick: Quicksort. Ph.D. Thesis, Stanford University, 1975."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-13345-3_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:52:37Z","timestamp":1578527557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-13345-3_29"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1984]]},"ISBN":["9783540133452","9783540388869"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-13345-3_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1984]]},"assertion":[{"value":"28 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}