dc.contributor.author | Matias, Yossi | |
dc.contributor.author | Segal, Eran | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-16T17:40:19Z | |
dc.date.available | 2011-03-16T17:40:19Z | |
dc.date.issued | 2006 | |
dc.identifier.citation | Y. Matias, E. Segal, and J. S. Vitter. “Efficient Bundle Sorting,” SIAM Journal on Computing, 36(2), 2006, 394–410. An extended abstract appears in Proceedings of the 11th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’00), San Francisco, CA, January 2000, 839–848. http://dx.doi.org/10.1137/S0097539704446554 | |
dc.identifier.uri | http://hdl.handle.net/1808/7178 | |
dc.description | AMS subject classification. 68W01
DOI. 10.1137/S0097539704446554 | |
dc.description.abstract | 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) logM/B 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 < c < 4. For moderately sized k, this bound circumvents the Θ((N/B) logM/B(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. | |
dc.language.iso | en_US | |
dc.publisher | Society for Industrial and Applied Mathematics | |
dc.subject | Sorting | |
dc.subject | External memory | |
dc.subject | Bundle sorting | |
dc.subject | Algorithms | |
dc.title | Efficient Bundle Sorting | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1137/S0097539704446554 | |
kusw.oaversion | Scholarly/refereed, publisher version | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |