{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T14:13:07Z","timestamp":1673359987559},"reference-count":24,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1996,8,1]],"date-time":"1996-08-01T00:00:00Z","timestamp":838857600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6194,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1996,8]]},"DOI":"10.1016\/0304-3975(95)00256-1","type":"journal-article","created":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T01:37:28Z","timestamp":1051753048000},"page":"211-238","source":"Crossref","is-referenced-by-count":9,"title":["Exploiting few inversions when sorting: Sequential and parallel algorithms"],"prefix":"10.1016","volume":"163","author":[{"given":"Christos","family":"Levcopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Petersson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(95)00256-1_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","article-title":"Sorting in c log n parallel steps","volume":"3","author":"Ajtai","year":"1983","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(95)00256-1_BIB2","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0020-0190(90)90212-G","article-title":"Sorting roughly sorted sequences in parallel","volume":"33","author":"Altaian","year":"1990","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(95)00256-1_BIB3","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0218014","article-title":"adaptive bitonic sorting: An optimal parallel algorithm for shared memory models","volume":"18","author":"Bilardi","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(95)00256-1_BIB4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(91)90179-L","article-title":"An Optimal parallel adaptive sorting algorithm","volume":"39","author":"Chen","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(95)00256-1_BIB5","series-title":"Proc. Joint Conf. on Vector and Parallel Processing","first-page":"539","article-title":"Improved parallel sorting of presorted flies","volume":"Vol. 634","author":"Chen","year":"1992"},{"key":"10.1016\/0304-3975(95)00256-1_BIB6","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","article-title":"Parallel merge sort","volume":"17","author":"Cole","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(95)00256-1_BIB7","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","article-title":"Approximate parallel scheduling. Part 1 : The basic technique with applications to optimal parallel list ranking in logarithmic time","volume":"17","author":"Cole","year":"1988","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(95)00256-1_BIB8","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0167-6423(82)90016-8","article-title":"Smoothsort, an alternative to sorting in situ","volume":"1","author":"Dijkstra","year":"1982","journal-title":"Sci. Comput. Programming"},{"key":"10.1016\/0304-3975(95)00256-1_BIB9","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/360680.360691","article-title":"Expected time bounds for selection","volume":"18","author":"Floyd","year":"1975","journal-title":"Comm. ACM"},{"key":"10.1016\/0304-3975(95)00256-1_BIB10","series-title":"Proc. 9th Ann. ACM Symp. on Theory of Computing","first-page":"49","article-title":"A new representation of linear lists","author":"Guibas","year":"1977"},{"key":"10.1016\/0304-3975(95)00256-1_BIB11","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","article-title":"A guided tour of Chernoff bounds","volume":"33","author":"Hagerup","year":"1989","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(95)00256-1_BIB12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0020-0190(83)90116-3","article-title":"Smoothsort's behaviour on presorted sequences","volume":"16","author":"Hertel","year":"1983","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(95)00256-1_BIB13","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1145\/42392.42403","article-title":"Practical in-place merging","volume":"31","author":"Huang","year":"1988","journal-title":"Comm. ACM"},{"key":"10.1016\/0304-3975(95)00256-1_BIB14","series-title":"An Introduction to Parallel Algorithms","author":"J\u00e1j\u00e1","year":"1992"},{"key":"10.1016\/0304-3975(95)00256-1_BIB15","article-title":"Sorting and Searching","volume":"Vol. 3","author":"Knuth","year":"1973"},{"key":"10.1016\/0304-3975(95)00256-1_BIB16","series-title":"Proc. 1st Scandinavian Workshop on Algorithm Theory","first-page":"14","article-title":"Implicit selection","volume":"Vol. 318","author":"Lai","year":"1988"},{"key":"10.1016\/0304-3975(95)00256-1_BIB17","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0020-0190(89)90139-7","article-title":"A note on adaptive parallel sorting","volume":"33","author":"Levcopoulos","year":"1989","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(95)00256-1_BIB18","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0020-0190(91)90181-G","article-title":"Splitsort \u2014 an adaptive sorting algorithm","volume":"39","author":"Levcopoulos","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(95)00256-1_BIB19","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1993.1021","article-title":"Adaptive Heapsort","volume":"14","author":"Levcopoulos","year":"1993","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(95)00256-1_BIB20","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TC.1985.5009382","article-title":"Measures of presortedness and optimal sorting algorithms","volume":"C-34","author":"Mannila","year":"1985","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(95)00256-1_BIB21","article-title":"Sorting and Searching","volume":"Vol. 1","author":"Mehlhorn","year":"1984"},{"key":"10.1016\/0304-3975(95)00256-1_BIB22","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0022-0000(86)90043-7","article-title":"An implicit data structure supporting insertion, deletion, and search in O(log2 n) time","volume":"33","author":"Munro","year":"1986","journal-title":"J. Comput. System. Sci."},{"key":"10.1016\/0304-3975(95)00256-1_BIB23_1","doi-asserted-by":"crossref","unstructured":"O. Petersson and A.M. Moffat, A framework for adaptive sorting, Discrete Applied Math., to appear.","DOI":"10.1007\/3-540-55706-7_38"},{"key":"10.1016\/0304-3975(95)00256-1_BIB23_2","series-title":"Proc. 3rd Scandinavian Workshop on Algorithm Theory","first-page":"422","volume":"Vol. 621","author":"Petersson","year":"1992"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397595002561?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397595002561?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T04:56:00Z","timestamp":1555390560000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0304397595002561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,8]]},"references-count":24,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1996,8]]}},"alternative-id":["0304397595002561"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(95)00256-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1996,8]]}}}