{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:17Z","timestamp":1792111457046,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":22,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_137","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:48:01Z","timestamp":1553100481000},"page":"708-715","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["External Sorting and Permuting"],"prefix":"10.1007","author":[{"given":"Jeffrey Scott","family":"Vitter","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"137_CR5404","unstructured":"Aggarwal A, Plaxton CG (1994) Optimal parallel sorting in multi-level storage. In: Proceedings of the 5th ACM-SIAM symposium on discrete algorithms, Arlington, vol\u00a05, pp\u00a0659\u2013668"},{"key":"137_CR5405","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal A, Vitter JS (1988) The input\/output complexity of sorting and related problems. Commun ACM 31:1116\u20131127","journal-title":"Commun ACM"},{"key":"137_CR5406","doi-asserted-by":"crossref","unstructured":"Arge L, Goodrich MT, Nelson M, Sitchinava N (2008) Fundamental parallel algorithms for private-cache chip multiprocessors. In: Proceedings of the 20th symposium on parallelism in algorithms and architectures, Munich, pp\u00a0197\u2013206","DOI":"10.1145\/1378533.1378573"},{"key":"137_CR5407","doi-asserted-by":"crossref","unstructured":"Arge L, Knudsen M, Larsen K (1993) A general lower bound on the I\/O-complexity of comparison-based algorithms. In: Proceedings of the workshop on algorithms and data structures, Montr\u00e9al. Lecture notes in computer science, vol\u00a0709, pp\u00a083\u201394","DOI":"10.1007\/3-540-57155-8_238"},{"key":"137_CR5408","doi-asserted-by":"crossref","unstructured":"Arge L, Thorup M (2013) RAM-efficient external memory sorting. In: Proceedings of the 24th international symposium on algorithms and computation, Hong Kong. Lecture notes in computer science, vol\u00a08283, pp\u00a0491\u2013501","DOI":"10.1007\/978-3-642-45030-3_46"},{"key":"137_CR5409","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1006\/jagm.2000.1089","volume":"36","author":"RD Barve","year":"2000","unstructured":"Barve RD, Kallahalla M, Varman PJ, Vitter JS (2000) Competitive analysis of buffer management algorithms. J Algorithms 36:152\u2013181","journal-title":"J Algorithms"},{"key":"137_CR5410","first-page":"189","volume":"35","author":"RD Barve","year":"2002","unstructured":"Barve RD, Vitter JS (2002) A simple and efficient parallel disk mergesort. ACM Trans Comput Syst 35:189\u2013215","journal-title":"ACM Trans Comput Syst"},{"key":"137_CR5411","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1137\/S0097539795283681","volume":"28","author":"TH Cormen","year":"1999","unstructured":"Cormen TH, Sundquist T, Wisniewski LF (1999) Asymptotically tight bounds for performing BMMC permutations on parallel disk systems. SIAM J Comput 28:105\u2013136","journal-title":"SIAM J Comput"},{"key":"137_CR5412","doi-asserted-by":"crossref","unstructured":"Dementiev R, Sanders P (2003) Asynchronous parallel disk sorting. In: Proceedings of the 15th ACM symposium on parallelism in algorithms and architectures, San Diego, pp\u00a0138\u2013148","DOI":"10.1145\/777412.777435"},{"key":"137_CR5413","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/S0097539703431573","volume":"34","author":"DA Hutchinson","year":"2005","unstructured":"Hutchinson DA, Sanders P, Vitter JS (2005) Duality between prefetching and queued writing with parallel disks. SIAM J Comput 34:1443\u20131463","journal-title":"SIAM J Comput"},{"key":"137_CR5414","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-004-1129-7","volume":"43","author":"M Kallahalla","year":"2005","unstructured":"Kallahalla M, Varman PJ (2005) Optimal read-once parallel disk scheduling. Algorithmica 43:309\u2013343","journal-title":"Algorithmica"},{"key":"137_CR5415","unstructured":"Knuth DE (1998) Sorting and searching. The art of computer programming, vol\u00a03, 2nd\u00a0edn. Addison-Wesley, Reading"},{"issue":"2","key":"137_CR5416","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/S0097539704446554","volume":"36","author":"Y Matias","year":"2006","unstructured":"Matias Y, Segal E, Vitter JS (2006) Efficient bundle sorting. SIAM J Comput 36(2):394\u2013410","journal-title":"SIAM J Comput"},{"key":"137_CR5417","doi-asserted-by":"crossref","unstructured":"Nodine MH, Vitter JS (1993) Deterministic distribution sort in shared and distributed memory multiprocessors. In: Proceedings of the 5th ACM symposium on parallel algorithms and architectures, Velen, vol\u00a05. ACM, pp\u00a0120\u2013129","DOI":"10.1145\/165231.165247"},{"key":"137_CR5418","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1145\/210332.210343","volume":"42","author":"MH Nodine","year":"1995","unstructured":"Nodine MH, Vitter JS (1995) Greed sort: an optimal sorting algorithm for multiple disks. J ACM 42:919\u2013933","journal-title":"J ACM"},{"key":"137_CR5419","doi-asserted-by":"crossref","unstructured":"Rahn M, Sanders P, Singler J (2010) Scalable distributed-memory external sorting. In: Proceedings of the 26th IEEE international conference on data engineering, Long Beach, pp\u00a0685\u2013688","DOI":"10.1109\/ICDE.2010.5447865"},{"key":"137_CR5420","doi-asserted-by":"crossref","unstructured":"Shah R, Varman PJ, Vitter JS (2004) Online algorithms for prefetching and caching on parallel disks. In: Proceedings of the 16th ACM symposium on parallel algorithms and architectures, Barcelona, pp\u00a0255\u2013264","DOI":"10.1145\/1007912.1007950"},{"issue":"9","key":"137_CR5421","doi-asserted-by":"publisher","first-page":"721","DOI":"10.14778\/2536360.2536371","volume":"6","author":"R Thonangi","year":"2013","unstructured":"Thonangi R, Yang J (2013) Permuting data on random-access block storage. Proc VLDB Endow 6(9):721\u2013732","journal-title":"Proc VLDB Endow"},{"issue":"2","key":"137_CR5422","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"JS Vitter","year":"2001","unstructured":"Vitter JS (2001) External memory algorithms and data structures: dealing with massive data. ACM Comput Surv 33(2):209\u2013271","journal-title":"ACM Comput Surv"},{"key":"137_CR5423","doi-asserted-by":"crossref","unstructured":"Vitter JS (2008) Algorithms and data structures for external memory. Series on foundations and trends in theoretical computer science. Now Publishers, Hanover. (Also referenced as Volume 2, Issue 4 of Foundations and trends in theoretical computer science, Now Publishers)","DOI":"10.1561\/0400000014"},{"key":"137_CR5424","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1145\/1162349.1162352","volume":"53","author":"JS Vitter","year":"2006","unstructured":"Vitter JS, Hutchinson DA (2006) Distribution sort with randomized cycling. J ACM 53:656\u2013680","journal-title":"J ACM"},{"key":"137_CR5425","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"JS Vitter","year":"1994","unstructured":"Vitter JS, Shriver EAM (1994) Algorithms for parallel memory I: two-level memories. Algorithmica 12:110\u2013147","journal-title":"Algorithmica"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:47:41Z","timestamp":1792108061000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_137","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}