{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:27Z","timestamp":1763468067691,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540180883"},{"type":"electronic","value":"9783540477471"}],"license":[{"start":{"date-parts":[[1987,1,1]],"date-time":"1987-01-01T00:00:00Z","timestamp":536457600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18088-5_40","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:26:50Z","timestamp":1330198010000},"page":"467-478","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The I\/O complexity of sorting and related problems"],"prefix":"10.1007","author":[{"given":"Alok","family":"Aggarwal","sequence":"first","affiliation":[]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"40_CR1","unstructured":"R. Beigel and J. Gill. Personal communication (1986)."},{"key":"40_CR2","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. \u201cTime Bounds for Selection,\u201d Journal of Computer and System Sciences, 7 (1973), 448\u2013461.","journal-title":"Journal of Computer and System Sciences"},{"key":"40_CR3","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-1-4684-2001-2_10","volume-title":"Complexity of Computer Calculations","author":"R. W. Floyd","year":"1972","unstructured":"R. W. Floyd. \u201cPermuting Information in Idealized Two-Level Storage,\u201d Complexity of Computer Calculations, Plenum, New York (1972), 105\u2013109."},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Hong J. W. and H. T. Kung. \u201cI\/O Complexity: The Red-Blue Pebble Game,\u201d Proceedings of the 13th Annual ACM Symposium on Theory of Computing, Milwaukee, WI (October 1981), 326\u2013333.","DOI":"10.1145\/800076.802486"},{"key":"40_CR5","volume-title":"Volume III: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth. The Art of Computer Programming. Volume III: Sorting and Searching. Addison-Wesley, Reading, MA (1973)."},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"F. T. Leighton. \u201cTight Bounds on the Complexity of Parallel Sorting,\u201d IEEE Transactions on Computers, C-34(4), Special Issue on Sorting (April 1985).","DOI":"10.1109\/TC.1985.5009385"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"E. E. Lindstrom and J. S. Vitter. \u201cThe Design and Analysis of BucketSort for Bubble Memory Secondary Storage,\u201d IEEE Transactions on Computers, C-34(3) (March 1985), 218\u2013233.","DOI":"10.1109\/TC.1985.1676565"},{"key":"40_CR8","first-page":"117","volume-title":"Advances in Computing Research, Volume 4: Special Issue on Parallel and Distributed Computing","author":"J. E. Savage","year":"1987","unstructured":"J. E. Savage and J. S. Vitter. \u201cParallelism in Space-Time Tradeoffs,\u201d Advances in Computing Research, Volume 4: Special Issue on Parallel and Distributed Computing, JAI Press, Greenwich, CT (1987), 117\u2013146."},{"issue":"5","key":"40_CR9","first-page":"324","volume":"30","author":"C. L. Wu","year":"1981","unstructured":"C. L. Wu and T. Y. Feng. \u201cThe Universality of the Shuffle-Exchange Network,\u201d IEEE Transactions on Computers, C-30(5) (May 1981), 324\u2013332.","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18088-5_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:36:45Z","timestamp":1742589405000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18088-5_40"}},"subtitle":["extended abstract"],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540180883","9783540477471"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-18088-5_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]},"assertion":[{"value":"29 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}