{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:09:21Z","timestamp":1792156161408,"version":"4.4.0"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>\n                    Many data sets to be sorted consist of a limited number of distinct keys. Sorting such data sets can be thought of as bundling together identical keys and having the bundles placed in order; we therefore denote this as bundle sorting. We describe an efficient algorithm for bundle sorting in external memory, which requires at most c(N\/B) log\n                    <jats:sub>M\/B<\/jats:sub>\n                    k disk accesses, where N is the number of keys, M is the size of internal memory, k is the number of distinct keys, B is the transfer block size, and 2 &lt; c &lt; 4. For moderately sized k, this bound circumvents the Theta((N\/B) log\n                    <jats:sub>M\/B<\/jats:sub>\n                    (N\/B)) I\/O lower bound known for general sorting. We show that our algorithm is optimal by proving a matching lower bound for bundle sorting. The improved running time of bundle sorting over general sorting can be significant in practice, as demonstrated by experimentation. An important feature of the new algorithm is that it is executed \"in-place,\" requiring no additional disk space.\n                  <\/jats:p>","DOI":"10.1137\/s0097539704446554","type":"journal-article","created":{"date-parts":[[2008,2,12]],"date-time":"2008-02-12T16:51:45Z","timestamp":1202835105000},"page":"394-410","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Bundle Sorting"],"prefix":"10.1137","volume":"36","author":[{"given":"Yossi","family":"Matias","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Segal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A. C. Arpaci\u2010Dussaeu, R. H. Arpaci\u2010Dussaeu, D. E. Culler, J. M. Hellerstein, and D. A. Patterson,\n                      High\u2010performance sorting on networks of workstations\n                      , in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1997, ACM, New York, 1997, pp. 243\u2013254.","DOI":"10.1145\/253260.253322"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"R. C. Agarwal,\n                      A super scalar sort algorithm for RISC processors\n                      , in Proceedings of the ACM SIGMOD International Conference on Management of Data, Montral, QC, 1996, ACM, New York, 1996, pp. 240\u2013246.","DOI":"10.1145\/233269.233336"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"R4","unstructured":"M. Beck, D. Bitton, and W. K. Wilkinson,\n                      Sorting Large Files on a Backend Multiprocessor\n                      , Technical Report 86\u2010741, Department of Computer Science, Cornell University, Ithaca, NY, 1986."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Baugsto, J. Greipsland, and J. Kamerbeek,\n                      Sorting large data files on POMA\n                      , in Proceedings of CONPAR\u201090: Proceedings of the Joint International Conference on Vector and Parallel Processing, Zurich, Switzerland, 1990, Springer\u2010Verlag, pp. 536\u2013547.","DOI":"10.1007\/3-540-53065-7_131"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Farach, P. Ferragina, and S. Muthukrishnan,\n                      Overcoming the memory bottleneck in suffix tree construction\n                      , in Proceedings of the 39th IEEE Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1998, IEEE Press, Piscataway, NJ, 1998, pp. 174\u2013183.","DOI":"10.1109\/SFCS.1998.743441"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"R8","unstructured":"IBM,\n                      Database 2, Administration Guide for Common Servers\n                      , Version 2, 1995."},{"key":"R9","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald","year":"1973"},{"key":"R10","unstructured":"Yossi Matias, Eran Segal, Jeffrey Vitter, Efficient bundle sorting, ACM, New York, 2000, 839\u20138481755546"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Jeffrey Vitter, External memory algorithms and data structures, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 50, Amer. Math. Soc., Providence, RI, 1999, 1\u2013382000i:68034","DOI":"10.1090\/dimacs\/050\/01"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Wang, J. S. Vitter, and B. R. Iyer,\n                      Scalable mining for classification rules in relational databases\n                      , in Proceedings of the International Database Engineering & Application Symposium, Cardiff, Wales, 1998, IEEE Computer Society Press, Washington, DC, pp. 58\u201367.","DOI":"10.1109\/IDEAS.1998.694358"},{"key":"R13","unstructured":"W. Zhang and P.\u2010A. Larson,\n                      Buffering and read\u2010ahead strategies for external mergesort\n                      , in Proceedings of the International Conference on Very Large Data Bases (VLDB), 1998, Morgan Kaufmann, San Francisco, CA, pp. 523\u2013533."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539704446554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:27:33Z","timestamp":1787336853000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539704446554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539704446554"],"URL":"https:\/\/doi.org\/10.1137\/s0097539704446554","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}