{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:52Z","timestamp":1750308772821,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002808","name":"Carlsbergfondet","doi-asserted-by":"publisher","award":["ANS-0257\/20"],"award-info":[{"award-number":["ANS-0257\/20"]}],"id":[{"id":"10.13039\/501100002808","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-1999-14186 (ALCOM-FT)"],"award-info":[{"award-number":["IST-1999-14186 (ALCOM-FT)"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort and compare the final algorithm with Quicksort, the established standard for comparison-based sorting, as well as with recent cache-aware proposals. The main result is a carefully implemented cache-oblivious sorting algorithm, which, our experiments show, can be faster than the best Quicksort implementation we are able to find for input sizes well within the limits of RAM. It is also at least as fast as the recent cache-aware implementations included in the test. On disk, the difference is even more pronounced regarding Quicksort and the cache-aware algorithms, whereas the algorithm is slower than a careful implementation of multiway Mergesort, such as TPIE.<\/jats:p>","DOI":"10.1145\/1227161.1227164","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"1-23","source":"Crossref","is-referenced-by-count":15,"title":["Engineering a cache-oblivious sorting algorithm"],"prefix":"10.1145","volume":"12","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[{"name":"University of Aarhus, \u00c5rhus N, Denmark"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}]},{"given":"Kristoffer","family":"Vinther","sequence":"additional","affiliation":[{"name":"Systematic Software Engineering A\/S, \u00c5rhus C, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/777792.777828"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/647911.740478"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509950"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/944618.944627"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Arge L. Brodal G. S. and Fagerberg R. 2005a. Cache-oblivious data structures. In Handbook of Data Structures and Applications D. Mehta and S. Sahni Eds. CRC Press Boca Ratom FL. Chapter 34.","DOI":"10.1201\/9781420035179.ch34"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064119"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064120"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740801"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684398"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740651"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796541"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545385"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946311"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074009"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142385"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380231105"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684422"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646345.689897"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780589"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109621"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545386"},{"key":"e_1_2_1_25_1","volume-title":"Proc. 9th Scandinavian Workshop on Algorithm Theory. LNCS","volume":"3111","author":"Brodal G. S.","unstructured":"Brodal, G. S., Fagerberg, R., Meyer, U., and Zeh, N. 2004. Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In Proc. 9th Scandinavian Workshop on Algorithm Theory. LNCS, vol. 3111. Springer, New York. 480--492."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_47"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007949"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109622"},{"key":"e_1_2_1_29_1","volume-title":"Duke University","author":"Department of Computer Science","year":"2002","unstructured":"Department of Computer Science, Duke University. 2002. TPIE: a transparent parallel I\/O environment. WWW page, http:\/\/www.cs.duke.edu\/TPIE\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_29"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982833"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759244"},{"key":"e_1_2_1_34_1","volume-title":"Proc. 8th International Workshop on Algorithms and Data Structures. LNCS","volume":"2748","author":"Franceschini G.","unstructured":"Franceschini, G. and Grossi, R. 2003b. Optimal worst-case operations for implicit cache-oblivious search trees. In Proc. 8th International Workshop on Algorithms and Data Structures. LNCS, vol. 2748. Springer, New York. 114--126."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_36_1","unstructured":"Gray J. 2003. Sort benchmark home page. WWW page http:\/\/research.microsoft.com\/barc\/SortBenchmark\/."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201004"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_46"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/280635"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/857152.857157"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0985"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/647258.720797"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384249"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1406996"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/512274.512284"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384245"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1227164","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1227164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1227164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":47,"alternative-id":["10.1145\/1227161.1227164"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1227164","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}