{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:46:22Z","timestamp":1725795982646},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319084039"},{"type":"electronic","value":"9783319084046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08404-6_3","type":"book-chapter","created":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T03:55:08Z","timestamp":1403668508000},"page":"26-37","source":"Crossref","is-referenced-by-count":1,"title":["Expected Linear Time Sorting for Word Size \u03a9(log2 n loglogn)"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper Sindahl","family":"Nielsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An $\\mathcal{O}(n \\log n)$ sorting network. In: STOC, pp. 1\u20139 (1983)","DOI":"10.1145\/800061.808726"},{"issue":"1","key":"3_CR2","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1006\/inco.1997.2632","volume":"136","author":"S. Albers","year":"1997","unstructured":"Albers, S., Hagerup, T.: Improved parallel integer sorting without concurrent writing. Inf. Comput.\u00a0136(1), 25\u201351 (1997)","journal-title":"Inf. Comput."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1006\/jcss.1998.1580","volume":"57","author":"A. Andersson","year":"1998","unstructured":"Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? Journal of Computer and System Sciences\u00a057, 74\u201393 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR4","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press and McGraw Hill (2009)"},{"issue":"1","key":"3_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jagm.1997.0873","volume":"25","author":"M. Dietzfelbinger","year":"1997","unstructured":"Dietzfelbinger, M., Hagerup, T., Katajainen, J., Penttonen, M.: A reliable randomized algorithm for the closest-pair problem. J. Algorithms\u00a025(1), 19\u201351 (1997)","journal-title":"J. Algorithms"},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string B-tree: A new data structure for string search in external memory and its applications. J. ACM\u00a046(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"issue":"6","key":"3_CR7","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/2049697.2049701","volume":"58","author":"M.T. Goodrich","year":"2011","unstructured":"Goodrich, M.T.: Randomized shellsort: A simple data-oblivious sorting algorithm. J. ACM\u00a058(6), 27 (2011)","journal-title":"J. ACM"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T.: Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in $\\mathcal{O}(n \\log n)$ time. CoRR, abs\/1403.2777 (2014)","DOI":"10.1145\/2591796.2591830"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: STACS, pp. 366\u2013398 (1998)","DOI":"10.1007\/BFb0028575"},{"key":"3_CR10","unstructured":"Han, Y., Thorup, M.: Integer sorting in $\\mathcal{O}(n \\sqrt{\\log \\log n})$ expected time and linear space. In: FOCS, pp. 135\u2013144 (2002)"},{"issue":"3","key":"3_CR11","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","volume":"28","author":"D. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D., Reisch, S.: Upper bounds for sorting integers on random access machines. Theoretical Computer Science\u00a028(3), 263\u2013276 (1983)","journal-title":"Theoretical Computer Science"},{"key":"3_CR12","unstructured":"Knuth, D.E.: The Art of Computer Programming, volume 4A: Combinatorial Algorithms. Addison-Wesley Professional (2011)"},{"key":"3_CR13","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. In: Packing, Spreading, and Monotone Routing Problems, ch.\u00a03.4.3, Morgan Kaufmann Publishers, Inc. (1991)"},{"issue":"1","key":"3_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539794268406","volume":"27","author":"T. Leighton","year":"1998","unstructured":"Leighton, T., Plaxton, C.G.: Hypercubic sorting networks. SIAM Journal on Computing\u00a027(1), 1\u201347 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"3_CR15","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/S0097539795288246","volume":"30","author":"M. Thorup","year":"2000","unstructured":"Thorup, M.: On RAM priority queues. SIAM J. Comput.\u00a030(1), 86\u2013109 (2000)","journal-title":"SIAM J. Comput."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Randomized sorting in $\\mathcal{O}(n \\log \\log n)$ time and linear space using addition, shift, and bit-wise boolean operations. J. Alg. 42(2), 205\u2013230 (2002)","DOI":"10.1006\/jagm.2002.1211"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time. In: FOCS, pp. 75\u201384 (1975)","DOI":"10.1109\/SFCS.1975.26"},{"key":"3_CR18","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u0398(n). Inf. Process. Lett. 17(2), 81\u201384 (1983)"},{"issue":"6","key":"3_CR19","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. CACM\u00a07(6), 347\u2013348 (1964)","journal-title":"CACM"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08404-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,9]],"date-time":"2022-04-09T06:32:33Z","timestamp":1649485953000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08404-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319084039","9783319084046"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08404-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}