{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:04:08Z","timestamp":1725663848732},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540558958"},{"type":"electronic","value":"9783540473060"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"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":[[1992]]},"DOI":"10.1007\/3-540-55895-0_452","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:43:16Z","timestamp":1330252996000},"page":"539-544","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved parallel sorting of presorted sequences"],"prefix":"10.1007","author":[{"given":"Jingsen","family":"Chen","sequence":"first","affiliation":[]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"62_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemeredi: Sorting in c log n parallel steps. Combinatorica\n3, 1\u201319 (1983)","journal-title":"Combinatorica"},{"key":"62_CR2","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0020-0190(90)90212-G","volume":"33","author":"T. Altman","year":"1989\/90","unstructured":"T. Altman and B. S. Chlebus: Sorting roughly sorted sequences in parallel. Information Processing Letters\n33, 297\u2013300 (1989\/90)","journal-title":"Information Processing Letters"},{"key":"62_CR3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0890-5401(91)90031-V","volume":"94","author":"P. C. P. P. Bhatt","year":"1991","unstructured":"P. C. P. Bhatt, K. Diks, T. Hagerup, V. C. Prasad, T. Radzik, and S. Saxena: Improved deterministic parallel integer sorting. Inform. Comput.\n94, 29\u201347 (1991)","journal-title":"Inform. Comput."},{"key":"62_CR4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(91)90179-L","volume":"39","author":"S. Carlsson","year":"1991","unstructured":"S. Carlsson and J. Chen: An optimal parallel adaptive sorting algorithm. Information Processing Letters\n39, 195\u2013200 (1991)","journal-title":"Information Processing Letters"},{"key":"62_CR5","unstructured":"J. Chen and S. Carlsson: On partitions and presortedness of sequences. Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 62\u201371 (1991)"},{"key":"62_CR6","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole: Parallel merge sort. SIAM Journal on Computing\n17, 770\u2013785 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"62_CR7","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin: Approximate parallel scheduling. Part I: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM Journal on Computing\n17, 128\u2013142 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"62_CR8","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 algorithm for nearly sorted lists. Communications of the ACM\n23, 620\u2013624 (1980)","journal-title":"Communications of the ACM"},{"key":"62_CR9","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 for sorting in situ. Science of Computer Programming\n1, 223\u2013233 (1982)","journal-title":"Science of Computer Programming"},{"key":"62_CR10","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1002\/spe.4380140603","volume":"14","author":"R. G. Dromey","year":"1984","unstructured":"R. G. Dromey: Exploiting partial order with quicksort. Software-Practice and Experience\n14, 509\u2013518 (1984)","journal-title":"Software-Practice and Experience"},{"key":"62_CR11","doi-asserted-by":"crossref","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\n83, 111\u2013119 (1989)","journal-title":"Information and Computation"},{"key":"62_CR12","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0020-0190(89)90139-7","volume":"33","author":"C. Levcopoulos","year":"1989","unstructured":"C. Levcopoulos and O. Petersson: A note on adaptive parallel sorting. Information Processing Letters\n33, 187\u2013191 (1989)","journal-title":"Information Processing Letters"},{"key":"62_CR13","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos and O. Petersson: An optimal parallel algorithm for sorting presorted files. Proc. 8th Conf. Found. Soft. Tech. Theore. Comput. Sci., 154\u2013160 (1988)","DOI":"10.1007\/3-540-50517-2_78"},{"key":"62_CR14","doi-asserted-by":"crossref","unstructured":"C. Levcopoulos and O. Petersson: Heapsort \u2014 adapted for presorted files. Proceedings of the First Workshop on Algorithms and Data Structures, 499\u2013509 (1989)","DOI":"10.1007\/3-540-51542-9_41"},{"key":"62_CR15","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\nC-34, 318\u2013325 (1985)","journal-title":"IEEE Transactions on Computers"},{"key":"62_CR16","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, 1984."},{"key":"62_CR17","volume-title":"Ph. D. Thesis","author":"O. Petersson","year":"1990","unstructured":"O. Petersson: Adaptive sorting. Ph. D. Thesis, Lund University, Sweden (1990)"},{"key":"62_CR18","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\n28, 775\u2013784 (1988)","journal-title":"BIT"}],"container-title":["Lecture Notes in Computer Science","Parallel Processing: CONPAR 92\u2014VAPP V"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55895-0_452","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:33:18Z","timestamp":1578526398000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55895-0_452"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540558958","9783540473060"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-55895-0_452","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"29 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}