{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T09:06:46Z","timestamp":1672304806601},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,30]],"date-time":"2007-10-30T00:00:00Z","timestamp":1193702400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2008,2]]},"DOI":"10.1007\/s00236-007-0061-0","type":"journal-article","created":{"date-parts":[[2007,10,29]],"date-time":"2007-10-29T06:05:24Z","timestamp":1193637924000},"page":"33-42","source":"Crossref","is-referenced-by-count":8,"title":["Adaptive sorting: an information theoretic perspective"],"prefix":"10.1007","volume":"45","author":[{"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[]},{"given":"Michael L.","family":"Fredman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,30]]},"reference":[{"key":"61_CR1","doi-asserted-by":"crossref","unstructured":"Andersson, A., Lai, T.W.: Fast updating of well-balanced trees. In: Proceedings of Scandinavian Workshop on Algorithm Theory, pp. 111\u2013121. Springer, Heidelberg (1990)","DOI":"10.1007\/3-540-52846-6_82"},{"key":"61_CR2","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0209045","volume":"9","author":"M. Brown","year":"1980","unstructured":"Brown M. and Tarjan R. (1980). Design and analysis of data structures for representing sorted lists. SIAM J. Comput. 9: 594\u2013614","journal-title":"SIAM J. Comput."},{"issue":"3","key":"61_CR3","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","volume":"5","author":"J. Bentley","year":"1976","unstructured":"Bentley J. and Yao A. (1976). An almost optimal algorithm for unbounded searching. Inf. Process. Lett. 5(3): 82\u201387","journal-title":"Inf. Process. Lett."},{"key":"61_CR4","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/BF01190160","volume":"9","author":"S. Carlsson","year":"1993","unstructured":"Carlsson S., Levcopoulos C. and Petersson O. (1993). Sublinear merging and natural Mergesort. Algorithmica 9: 629\u2013648","journal-title":"Algorithmica"},{"key":"61_CR5","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1137\/S009753979732699X","volume":"30","author":"R. Cole","year":"2000","unstructured":"Cole R. (2000). On the dynamic finger conjecture for splay trees. Part II: The proof. SIAM J. Comput. 30: 44\u201385","journal-title":"SIAM J. Comput."},{"key":"61_CR6","unstructured":"Elmasry, A.: Priority Queues, Pairing and Adaptive Sorting. 29th ICALP. LNCS, vol. 2380, pp. 183\u2013194 (2002)"},{"issue":"4","key":"61_CR7","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V. Estivill-Castro","year":"1992","unstructured":"Estivill-Castro V. (1992). A survey of adaptive sorting algorithms. ACM Comput. Surv. 24(4): 441\u2013476","journal-title":"ACM Comput. Surv."},{"key":"61_CR8","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0890-5401(89)90050-3","volume":"83","author":"V. Estivill-Castro","year":"1989","unstructured":"Estivill-Castro V. and Wood D. (1989). A new measure of presortedness. Inf. Comput. 83: 111\u2013119","journal-title":"Inf. Comput."},{"key":"61_CR9","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M. Fredman","year":"1976","unstructured":"Fredman M. (1976). How good is the information theory bound in sorting?. Theor. Comput. Sci. 1: 355\u2013361","journal-title":"Theor. Comput. Sci."},{"key":"61_CR10","first-page":"49","volume":"9","author":"L. Guibas","year":"1977","unstructured":"Guibas L., McCreight E., Plass M. and Roberts J. (1977). A new representation of linear lists. ACM Symp. Theory Comput. 9: 49\u201360","journal-title":"ACM Symp. Theory Comput."},{"key":"61_CR11","unstructured":"Knuth, D.: The Art of Computer Programming: Sorting and Searching, vol. III, 2nd edn. Addison-wesley (1998)"},{"key":"61_CR12","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0020-0190(91)90181-G","volume":"39","author":"C. Levcopoulos","year":"1991","unstructured":"Levcopoulos C. and Petersson O. (1991). Splitsort\u2014an adaptive sorting algorithm. Inf. Process. Lett. 39: 205\u2013211","journal-title":"Inf. Process. Lett."},{"key":"61_CR13","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1993.1021","volume":"14","author":"C. Levcopoulos","year":"1993","unstructured":"Levcopoulos C. and Petersson O. (1993). Adaptive heapsort. J. Algorithms 14: 395\u2013413","journal-title":"J. Algorithms"},{"key":"61_CR14","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1006\/inco.1994.1050","volume":"112","author":"C. Levcopoulos","year":"1994","unstructured":"Levcopoulos C. and Petersson O. (1994). Sorting shuffled monotone sequences. Inf. Comput. 112: 37\u201350","journal-title":"Inf. Comput."},{"key":"61_CR15","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0304-3975(95)00256-1","volume":"163","author":"C. Levcopoulos","year":"1996","unstructured":"Levcopoulos C. and Petersson O. (1996). Exploiting few inversions when sorting: Sequential and parallel algorithms. Theor. Comput. Sci. 163: 211\u2013238","journal-title":"Theor. Comput. Sci."},{"key":"61_CR16","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"C-34","author":"H. Mannila","year":"1985","unstructured":"Mannila H. (1985). Measures of presortedness and optimal sorting algorithms. IEEE Trans. Comput. C-34: 318\u2013325","journal-title":"IEEE Trans. Comput."},{"key":"61_CR17","volume-title":"Data Structures and Algorithms. Sorting and Searching, vol. 1","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn K. (1984). Data Structures and Algorithms. Sorting and Searching, vol. 1. Springer, Berlin"},{"key":"61_CR18","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Sorting presorted files. In: Proceedings Of the 4th GI Conference on Theory of Computer Science. LNCS, vol. 67, pp. 199\u2013212 (1979)","DOI":"10.1007\/3-540-09118-1_22"},{"key":"61_CR19","doi-asserted-by":"crossref","unstructured":"Moffat, A., Petersson, O., Wormald, N.: A Tree-based Mergesort. Acta Informatica, pp. 775\u2013793. Springer, Heidelberg (1998)","DOI":"10.1007\/s002360050142"},{"key":"61_CR20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0166-218X(93)E0160-Z","volume":"59","author":"O. Petersson","year":"1995","unstructured":"Petersson O. and Moffat A. (1995). A framework for adaptive sorting. Discrete Appl. Math. 59: 153\u2013179","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"61_CR21","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. Sleator","year":"1985","unstructured":"Sleator D. and Tarjan R. (1985). Self-adjusting binary search trees. J. ACM 32(3): 652\u2013686","journal-title":"J. ACM"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0061-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-007-0061-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0061-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T13:41:54Z","timestamp":1558705314000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-007-0061-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,30]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["61"],"URL":"https:\/\/doi.org\/10.1007\/s00236-007-0061-0","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,30]]}}}