{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:39Z","timestamp":1725663279647},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540528463"},{"type":"electronic","value":"9783540471646"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52846-6_88","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:43:30Z","timestamp":1330188210000},"page":"181-191","source":"Crossref","is-referenced-by-count":9,"title":["Sorting shuffled monotone sequences"],"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,6,8]]},"reference":[{"key":"16_CR1","volume-title":"Data Structures and Algorithms","author":"A.V. Aho","year":"1983","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, Mass., 1983."},{"issue":"5\/6","key":"16_CR2","first-page":"263","volume":"22","author":"A. Brandst\u00e4dt","year":"1986","unstructured":"A. Brandst\u00e4dt and D. Kratsch. On partitions of permutations into increasing and decreasing subsequences. Journal of Information Processing and Cybernetics, 22(5\/6):263\u2013273, 1986.","journal-title":"Journal of Information Processing and Cybernetics"},{"doi-asserted-by":"crossref","unstructured":"S. Carlsson, C. Levcopoulos, and O. Petersson. Sublinear merging and Natural Merge Sort. In Proc. SIGAL International Symposium on Algorithms. LNCS, Springer-Verlag, 1990. To appear.","key":"16_CR3","DOI":"10.1007\/3-540-52921-7_74"},{"issue":"11","key":"16_CR4","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"},{"issue":"6","key":"16_CR5","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1002\/spe.4380140603","volume":"14","author":"G.R. Dromey","year":"1984","unstructured":"G.R. Dromey. Exploiting partial order with Quicksort. Software\u2014Practice and Experience, 14(6):509\u2013518, 1984.","journal-title":"Software\u2014Practice and Experience"},{"key":"16_CR6","series-title":"Research Report","volume-title":"Right invariant metrics and measures of presortedness","author":"V. Estivill-Castro","year":"1989","unstructured":"V. Estivill-Castro, H. Mannila, and D. Wood. Right invariant metrics and measures of presortedness. Research Report CS-89-30, University of Waterloo, Department of Computer Science, Waterloo, Canada, 1989."},{"issue":"1","key":"16_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0890-5401(89)90050-3","volume":"83","author":"V. Estivill-Castro","year":"1989","unstructured":"V. Estivill-Castro and D. Wood. A new measure of presortedness. Information and Computation, 83(1):111\u2013119, 1989.","journal-title":"Information and Computation"},{"key":"16_CR8","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M.L. Fredman","year":"1975","unstructured":"M.L. Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11:29\u201335, 1975.","journal-title":"Discrete Mathematics"},{"key":"16_CR9","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":"16_CR10","first-page":"499","volume":"382","author":"C. Levcopoulos","year":"1989","unstructured":"C. Levcopoulos and O. Petersson. Heapsort\u2014adapted for presorted files. In Proc. 1989 Workshop on Algorithms and Data tructures, pages 499\u2013509. LNCS 382, Springer-Verlag, 1989.","journal-title":"LNCS"},{"unstructured":"C. Levcopoulos and O. Petersson. Splitsort\u2014an adaptive sorting algorithm. In Proc. Fifteenth Symposium on Mathematical Foundations of Computer Science. LNCS, Springer-Verlag, 1990. To appear.","key":"16_CR11"},{"issue":"4","key":"16_CR12","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":"16_CR13","first-page":"199","volume":"67","author":"K. Mehlhorn","year":"1979","unstructured":"K. Mehlhorn. Sorting presorted files. In Proc. 4th GI Conference on Theoretical Computer Science, pages 199\u2013212. LNCS 67, Springer-Verlag, 1979.","journal-title":"LNCS"},{"key":"16_CR14","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":"16_CR15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.4153\/CJM-1961-015-3","volume":"13","author":"C. Schensted","year":"1961","unstructured":"C. Schensted. Longest increasing and decreasing subsequences. Canadian Journal of Mathematics, 13:179\u2013191, 1961.","journal-title":"Canadian Journal of Mathematics"},{"issue":"4","key":"16_CR16","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(4):775\u2013784, 1988.","journal-title":"BIT"},{"issue":"12","key":"16_CR17","first-page":"633","volume":"20","author":"K. Wagner","year":"1984","unstructured":"K. Wagner. Monotonic coverings of finite sets. Journal of Information Processing and Cybernetics, 20(12):633\u2013639, 1984.","journal-title":"Journal of Information Processing and Cybernetics"},{"issue":"4","key":"16_CR18","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1145\/3341.3348","volume":"28","author":"R.L. Wainwright","year":"1985","unstructured":"R.L. Wainwright. A class of sorting algorithms based on Quicksort. Communications of the ACM, 28(4):396\u2013402, 1985.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","SWAT 90"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52846-6_88.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:09:32Z","timestamp":1619557772000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52846-6_88"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540528463","9783540471646"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-52846-6_88","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}