{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T10:40:29Z","timestamp":1725532829425},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642020100"},{"type":"electronic","value":"9783642020117"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02011-7_25","type":"book-chapter","created":{"date-parts":[[2009,6,2]],"date-time":"2009-06-02T05:12:20Z","timestamp":1243919540000},"page":"269-280","source":"Crossref","is-referenced-by-count":2,"title":["Bulk-Insertion Sort: Towards Composite Measures of Presortedness"],"prefix":"10.1007","author":[{"given":"Riku","family":"Saikkonen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eljas","family":"Soisalon-Soininen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"25_CR1","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V. Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Computing Surveys\u00a024(4), 441\u2013476 (1992)","journal-title":"ACM Computing Surveys"},{"issue":"2","key":"25_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0166-218X(93)E0160-Z","volume":"59","author":"O. Petersson","year":"1995","unstructured":"Petersson, O., Moffat, A.: A framework for adaptive sorting. Discrete Applied Mathematics\u00a059(2), 153\u2013179 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"C-34","author":"H. Mannila","year":"1985","unstructured":"Mannila, H.: Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers\u00a0C-34, 318\u2013325 (1985)","journal-title":"IEEE Transactions on Computers"},{"key":"25_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/3-540-09118-1_22","volume-title":"4th GI-Conference on Theoretical Computer Science","author":"K. Mehlhorn","year":"1979","unstructured":"Mehlhorn, K.: Sorting presorted files. In: Weihrauch, K. (ed.) GI-TCS 1979. LNCS, vol.\u00a067, pp. 199\u2013212. Springer, Heidelberg (1979)"},{"key":"25_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. Springer, Heidelberg (1984)"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0019-9958(85)80034-6","volume":"67","author":"A.K. Tsakalidis","year":"1985","unstructured":"Tsakalidis, A.K.: AVL-trees for localized search. Information and Control\u00a067, 173\u2013194 (1985)","journal-title":"Information and Control"},{"key":"25_CR7","first-page":"307","volume-title":"IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (IFIP TCS 2004)","author":"A. Elmasry","year":"2004","unstructured":"Elmasry, A.: Adaptive sorting with AVL trees. In: IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (IFIP TCS 2004), pp. 307\u2013316. Kluwer, Dordrecht (2004)"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00236-007-0061-0","volume":"45","author":"A. Elmasry","year":"2008","unstructured":"Elmasry, A., Fredman, M.L.: Adaptive sorting: an information theoretic perspective. Acta Informatica\u00a045, 33\u201342 (2008)","journal-title":"Acta Informatica"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/3-540-45471-3_45","volume-title":"Algorithm Theory - SWAT 2002","author":"E. Soisalon-Soininen","year":"2002","unstructured":"Soisalon-Soininen, E., Widmayer, P.: Amortized complexity of bulk updates in AVL-trees. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 439\u2013448. Springer, Heidelberg (2002)"},{"key":"25_CR10","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s00236-002-0086-3","volume":"38","author":"K.S. Larsen","year":"2002","unstructured":"Larsen, K.S.: Relaxed red-black trees with group updates. Acta Informatica\u00a038, 565\u2013586 (2002)","journal-title":"Acta Informatica"},{"key":"25_CR11","first-page":"374","volume-title":"14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)","author":"G.E. Blelloch","year":"2003","unstructured":"Blelloch, G.E., Maggs, B.M., Woo, S.L.M.: Space-efficient finger search on degree-balanced search trees. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 374\u2013383. ACM Press, New York (2003)"},{"issue":"1","key":"25_CR12","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/S009753979732699X","volume":"30","author":"R. Cole","year":"2000","unstructured":"Cole, R.: On the dynamic finger conjecture for splay trees, part II: The proof. SIAM Journal on Computing\u00a030(1), 44\u201385 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"Huddleston, S., Mehlhorn, K.: A new data structure for representing sorted lists. Acta Informatica\u00a017, 157\u2013184 (1982)","journal-title":"Acta Informatica"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-51859-2_19","volume-title":"International Symposium on Optimal Algorithms","author":"J. Katajainen","year":"1989","unstructured":"Katajainen, J., Levcopoulos, C., Petersson, O.: Local insertion sort revisited. In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol.\u00a0401, pp. 239\u2013253. Springer, Heidelberg (1989)"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/BF01190160","volume":"9","author":"S. Carlsson","year":"1993","unstructured":"Carlsson, S., Levcopoulos, C., Petersson, O.: Sublinear merging and natural mergesort. Algorithmica\u00a09, 629\u2013648 (1993)","journal-title":"Algorithmica"},{"issue":"7","key":"25_CR16","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1002\/(SICI)1097-024X(199607)26:7<781::AID-SPE35>3.0.CO;2-B","volume":"126","author":"A. Moffat","year":"1996","unstructured":"Moffat, A., Eddy, G., Petersson, O.: Splaysort: Fast, versatile, practical. Software, Practice and Experience\u00a0126(7), 781\u2013797 (1996)","journal-title":"Software, Practice and Experience"},{"key":"25_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(91)90181-G","volume":"39","author":"C. Levcopoulos","year":"1991","unstructured":"Levcopoulos, C., Petersson, O.: Splitsort \u2013 an adaptive sorting algorithm. Information Processing Letters\u00a039, 205\u2013211 (1991)","journal-title":"Information Processing Letters"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/11427186_52","volume-title":"Experimental and Efficient Algorithms","author":"A. Elmasry","year":"2005","unstructured":"Elmasry, A., Hammad, A.: An empirical study for inversions-sensitive sorting algorithms. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 597\u2013601. Springer, Heidelberg (2005)"},{"key":"25_CR19","unstructured":"Brodal, G.S., Fagerberg, R., Moruz, G.: On the adaptiveness of quicksort. In: 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), Society for Industrial and Applied Mathematics, pp. 130\u2013140 (2005)"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.entcs.2003.12.006","volume":"91","author":"V. Estivill-Castro","year":"2004","unstructured":"Estivill-Castro, V.: Generating nearly sorted sequences \u2013 the use of measures of disorder. Electronic Notes in Theoretical Computer Science\u00a091, 56\u201395 (2004)","journal-title":"Electronic Notes in Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02011-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T11:09:56Z","timestamp":1552043396000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02011-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020100","9783642020117"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02011-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}