{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:21:22Z","timestamp":1725549682090},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281016"},{"type":"electronic","value":"9783540317111"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11534273_34","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T08:31:47Z","timestamp":1268382707000},"page":"385-395","source":"Crossref","is-referenced-by-count":8,"title":["Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Moruz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"34_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/11561071","volume-title":"Proc. 32nd International Colloquium on 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: Proc. 32nd International Colloquium on Automata, Languages, and Programming. LNCS, Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Moruz, G.: On the adaptiveness of quicksort. In: Proc. 7th Workshop on Algorithm Engineering and Experiments. SIAM, Philadelphia (2005)","key":"34_CR2","DOI":"10.7146\/brics.v11i27.21852"},{"issue":"2","key":"34_CR3","first-page":"249","volume":"18","author":"A. Colin","year":"2000","unstructured":"Colin, A., Puaut, I.: Worst case execution time for a processor with branch prediction. Real-Time Systems, Special issue on worst-case execution time analysis\u00a018(2), 249\u2013274 (2000)","journal-title":"Real-Time Systems, Special issue on worst-case execution time analysis"},{"key":"34_CR4","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"34_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54029-6_153","volume-title":"Advances in Computing and Information - ICCI \u201991","author":"V. Estivill-Castro","year":"1991","unstructured":"Estivill-Castro, V., Wood, D.: Practical adaptive sorting. In: Dehne, F., Fiala, F., Koczkodaj, W.W. (eds.) ICCI 1991. LNCS, vol.\u00a0497, pp. 47\u201354. Springer, Heidelberg (1991)"},{"issue":"4","key":"34_CR6","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 Surverys\u00a024(4), 441\u2013475 (1992)","journal-title":"ACM Computing Surverys"},{"issue":"12","key":"34_CR7","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/355588.365103","volume":"7","author":"R.W. Floyd","year":"1964","unstructured":"Floyd, R.W.: Algorithm 245: Treesort3. Communications of the ACM\u00a07(12), 701 (1964)","journal-title":"Communications of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Guibas, L.J., McCreight, E.M., Plass, M.F., Roberts, J.R.: A new representation of linear lists. In: Proc. 9th Ann. ACM Symposium on Theory of Computing, pp. 49\u201360 (1977)","key":"34_CR8","DOI":"10.1145\/800105.803395"},{"key":"34_CR9","volume-title":"Computer Architecture: A Quantitative Approach","author":"J.L. Hennesy","year":"1996","unstructured":"Hennesy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco (1996)"},{"issue":"1","key":"34_CR10","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(1), 205\u2013211 (1991)","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Li, X., Mitra, T., Roychoudhury, A.: Modeling control speculation for timing analysis. Real-Time Systems Journal\u00a029(1) (January 2005)","key":"34_CR11","DOI":"10.1023\/B:TIME.0000048933.15922.f9"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"34","author":"H. Manilla","year":"1985","unstructured":"Manilla, H.: Measures of presortedness and optimal sorting algorithms. IEEE Trans. Comput.\u00a034, 318\u2013325 (1985)","journal-title":"IEEE Trans. Comput."},{"unstructured":"McFarling, S.: Combining branch predictors. Technical report, Western Research Laboratory (1993)","key":"34_CR13"},{"key":"34_CR14","volume-title":"Data structures and algorithms. Sorting and searching","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data structures and algorithms. Sorting and searching, vol.\u00a01. Springer, Heidelberg (1984)"},{"key":"34_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1007\/978-3-540-30140-0_69","volume-title":"Algorithms \u2013 ESA 2004","author":"P. Sanders","year":"2004","unstructured":"Sanders, P., Winkel, S.: Super scalar sample sort. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 784\u2013796. Springer, Heidelberg (2004)"},{"issue":"6","key":"34_CR16","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. Communications of the ACM\u00a07(6), 347\u2013348 (1964)","journal-title":"Communications of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Yeh, Y.-Y., Patt, Y.N.: Alternative implementations of two-level adaptive branch prediction. In: ACM International Symposium on Computer Architecture, ISCA (1992)","key":"34_CR17","DOI":"10.1145\/139669.139709"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11534273_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,24]],"date-time":"2021-10-24T15:16:53Z","timestamp":1635088613000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11534273_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281016","9783540317111"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11534273_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}