{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T10:53:07Z","timestamp":1742986387869,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642250101"},{"type":"electronic","value":"9783642250118"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-25011-8_16","type":"book-chapter","created":{"date-parts":[[2011,11,9]],"date-time":"2011-11-09T01:27:34Z","timestamp":1320802054000},"page":"195-208","source":"Crossref","is-referenced-by-count":1,"title":["Two Constant-Factor-Optimal Realizations of Adaptive Heapsort"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Edelkamp","sequence":"first","affiliation":[]},{"given":"Amr","family":"Elmasry","sequence":"additional","affiliation":[]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1007\/11523468_47","volume-title":"Automata, Languages and Programming","author":"G.S. Brodal","year":"2005","unstructured":"Brodal, G.S., Fagerberg, R., Moruz, G.: Cache-Aware and Cache-Oblivious Adaptive Sorting. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 576\u2013588. Springer, Heidelberg (2005)"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Moruz, G.: On the Adaptiveness of Quicksort. ACM J. Exp. Algorithmics\u00a012, Article 3.2 (2008)","DOI":"10.1145\/1227161.1402294"},{"issue":"6","key":"16_CR3","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(6), 629\u2013648 (1993)","journal-title":"Algorithmica"},{"issue":"3","key":"16_CR4","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/BF01990520","volume":"33","author":"R.D. Dutton","year":"1993","unstructured":"Dutton, R.D.: Weak-heap Sort. BIT\u00a033(3), 372\u2013381 (1993)","journal-title":"BIT"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/3-540-46541-3_21","volume-title":"STACS 2000","author":"S. Edelkamp","year":"2000","unstructured":"Edelkamp, S., Wegener, I.: On the Performance of Weak-Heapsort. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 254\u2013266. Springer, Heidelberg (2000)"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/3-540-45465-9_17","volume-title":"Automata, Languages and Programming","author":"A. Elmasry","year":"2002","unstructured":"Elmasry, A.: Priority Queues, Pairing and Adaptive Sorting. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 183\u2013194. Springer, Heidelberg (2002)"},{"key":"16_CR7","first-page":"315","volume-title":"IFIP Int. Fed. Inf. Process.","author":"A. Elmasry","year":"2004","unstructured":"Elmasry, A.: Adaptive Sorting with AVL Trees. In: IFIP Int. Fed. Inf. Process., vol.\u00a0155, pp. 315\u2013324. Springer, New York (2004)"},{"issue":"1","key":"16_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. Inform.\u00a045(1), 33\u201342 (2008)","journal-title":"Acta. Inform."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Elmasry, A., Hammad, A.: Inversion-sensitive Sorting Algorithms in Practice. ACM J. Exp. Algorithmics\u00a013, Article 1.11 (2009)","DOI":"10.1145\/1412228.1455267"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Elmasry, A., Jensen, C., Katajainen, J.: Multipartite Priority Queues. ACM Trans. Algorithms\u00a05(1), Article 14 (2008)","DOI":"10.1145\/1435375.1435389"},{"key":"16_CR11","first-page":"135","volume-title":"16th Annual ACM Symposium on Theory of Computing","author":"H.N. Gabow","year":"1984","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and Related Techniques for Geometry Problems. In: 16th Annual ACM Symposium on Theory of Computing, pp. 135\u2013143. ACM, New York (1984)"},{"key":"16_CR12","first-page":"49","volume-title":"9th Annual ACM Symposium on Theory of Computing","author":"L.J. Guibas","year":"1977","unstructured":"Guibas, L.J., McCreight, E.M., Plass, M.F., Roberts, J.R.: A New Representation for Linear Lists. In: 9th Annual ACM Symposium on Theory of Computing, pp. 49\u201360. ACM, New York (1977)"},{"issue":"1","key":"16_CR13","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"C.A.R. Hoare","year":"1962","unstructured":"Hoare, C.A.R.: Quicksort. Comput. J.\u00a05(1), 10\u201316 (1962)","journal-title":"Comput. J."},{"key":"16_CR14","volume-title":"Sorting and Searching, The Art of Computer Programming","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, The Art of Computer Programming, 2nd edn., vol.\u00a03. Addison Wesley Longman, Reading (1998)","edition":"2"},{"issue":"3","key":"16_CR15","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1006\/jagm.1993.1021","volume":"14","author":"C. Levcopoulos","year":"1993","unstructured":"Levcopoulos, C., Petersson, O.: Adaptive Heapsort. J. Algorithms\u00a014(3), 395\u2013413 (1993)","journal-title":"J. Algorithms"},{"issue":"4","key":"16_CR16","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: An Adaptive Sorting Algorithm. Inform. Process. Lett.\u00a039(4), 205\u2013211 (1991)","journal-title":"Inform. Process. Lett."},{"issue":"1-2","key":"16_CR17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0304-3975(95)00256-1","volume":"163","author":"C. Levcopoulos","year":"1996","unstructured":"Levcopoulos, C., Petersson, O.: Exploiting Few Inversions When Sorting: Sequential and Parallel Algorithms. Theoret. Comput. Sci.\u00a0163(1-2), 211\u2013238 (1996)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"16_CR18","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 Trans. Comput.\u00a0C-34(4), 318\u2013325 (1985)","journal-title":"IEEE Trans. Comput."},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/3-540-09118-1_22","volume-title":"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)"},{"issue":"7","key":"16_CR20","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 Pract. Exper.\u00a0126(7), 781\u2013797 (1996)","journal-title":"Software Pract. Exper."},{"issue":"9","key":"16_CR21","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1007\/s002360050142","volume":"35","author":"A. Moffat","year":"1998","unstructured":"Moffat, A., Petersson, O., Wormald, N.C.: A Tree-based Mergesort. Acta Inform.\u00a035(9), 775\u2013793 (1998)","journal-title":"Acta Inform."},{"issue":"8","key":"16_CR22","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#","volume":"27","author":"D.R. Musser","year":"1997","unstructured":"Musser, D.R.: Introspective Sorting and Selection Algorithms. Software Pract. Exper.\u00a027(8), 983\u2013993 (1997)","journal-title":"Software Pract. Exper."},{"key":"16_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-642-02011-7_25","volume-title":"Experimental Algorithms","author":"R. Saikkonen","year":"2009","unstructured":"Saikkonen, R., Soisalon-Soininen, E.: Bulk-Insertion Sort: Towards Composite Measures of Presortedness. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol.\u00a05526, pp. 269\u2013280. Springer, Heidelberg (2009)"},{"issue":"4","key":"16_CR24","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1145\/359460.359478","volume":"21","author":"J. Vuillemin","year":"1978","unstructured":"Vuillemin, J.: A Data Structure for Manipulating Priority Queues. Commun. ACM\u00a021(4), 309\u2013315 (1978)","journal-title":"Commun. ACM"},{"issue":"4","key":"16_CR25","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A Unifying Look at Data Structures. Commun. ACM\u00a023(4), 229\u2013239 (1980)","journal-title":"Commun. ACM"},{"issue":"6","key":"16_CR26","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: Heapsort. Commun. ACM\u00a07(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25011-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,15]],"date-time":"2021-12-15T19:14:22Z","timestamp":1639595662000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25011-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642250101","9783642250118"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25011-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}