{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:11Z","timestamp":1775282291000,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540571551","type":"print"},{"value":"9783540479185","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_238","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:05:03Z","timestamp":1330257903000},"page":"83-94","source":"Crossref","is-referenced-by-count":19,"title":["A general lower bound on the I\/O-complexity of comparison-based algorithms"],"prefix":"10.1007","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[]},{"given":"Mikael","family":"Knudsen","sequence":"additional","affiliation":[]},{"given":"Kirsten","family":"Larsen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"10_CR1","unstructured":"Aggarwal, A., Vitter, J.S.: The I\/O Complexity of Sorting and Related Problems. Proceedings of 14th ICALP (1987), Lecture Notes in Computer Science 267, Springer Verlag, 467\u2013478, and: The Input\/Output Complexity of Sorting and Related Problems. Communications of the ACM, Vol 31 (9) (1988) 1116\u20131127."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. Proceedings of 15th STOC (1983), 80\u201386.","DOI":"10.1145\/800061.808735"},{"issue":"4","key":"10_CR3","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1972","unstructured":"Blum, M., Floyd, R.W, Pratt, V.R, Rivest, R.L, Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences, 7(4) (1972), 448\u2013461.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR4","unstructured":"Knudsen, M., Larsen, K.,: I\/O-complexity of comparison and permutation problems. M.Sc. Thesis, Aarhus University, November 1992."},{"key":"10_CR5","unstructured":"Knuth, D.E.: The Art of Computer Programming, Vol 3: Sorting and Searching, Addison-Wesley (1973) (p. 205\u2013206)."},{"key":"10_CR6","unstructured":"Misra, J., Gries, D.: Finding Repeated Elements. Science of Computer Programming 2 (1982), 143\u2013152, North-Holland Publishing."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Raman, V.: Sorting Multisets and Vectors In-Place. Proceedings of 2nd WADS, Lecture Notes in Computer Science 519, Springer Verlag (1991), 473\u2013479.","DOI":"10.1007\/BFb0028285"},{"issue":"1","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"I. Munro","year":"1976","unstructured":"Munro, I., Spira, P.M.: Sorting and Searching in Multisets. SIAM Journal of Computing, 5 (1) (1976) 1\u20138.","journal-title":"SIAM Journal of Computing"},{"key":"10_CR9","unstructured":"Nodine, M.H., Vitter, J.S.: Optimal Deterministic Sorting on Parallel Disks. Brown University, CS-92-08, August 1992."},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Vitter, J.S: Efficient Memory Access in Large-Scale Computation (invited paper). Proceedings of 8th STACS (1991), 26\u201341.","DOI":"10.1007\/BFb0020785"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Vitter, J.S., Shriver, E.A.M.: Optimal Disk I\/O with Parallel Block Transfer. Proceedings of 22nd STOC (1990), 159\u2013169.","DOI":"10.1145\/100216.100234"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_238.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:08:13Z","timestamp":1605647293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_238","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}