{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:34Z","timestamp":1725664714195},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_131","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:36:34Z","timestamp":1330274194000},"page":"185-197","source":"Crossref","is-referenced-by-count":3,"title":["Sorting and searching revisted"],"prefix":"10.1007","author":[{"given":"Arne","family":"Andersson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"17_CR1","unstructured":"S. Albers and T. Hagerup. Improved parallel integer sorting without concurrent writing. In Proc. 3rd ACM-SIAM SODA, pages 463\u2013472, 1992."},{"key":"17_CR2","unstructured":"A. Andersson. Faster deterministic sorting and searching in linear space. Tech. report LU-CS-TR:95-160, Lund University, 1995."},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"A. Andersson. Sublogarithmic searching without multiplications. In Proc. 36th IEEE Symposium on Foundations of Computer Science, pages 655\u2013663. ACM Press, 1995.","DOI":"10.1109\/SFCS.1995.492667"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In Proceedings 27th ACM Symposium on Theory of Computing, pages 427\u2013436. ACM Press, 1995.","DOI":"10.1145\/225058.225173"},{"key":"17_CR5","unstructured":"A. Andersson, P.B. Miltersen, and M. Thorup. Manuscript. In preparation, 1996."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"A. Andersson and S. Nilsson. A new efficient radix sort. In Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, pages 714\u2013721. IEEE Computer Society Press, 1994.","DOI":"10.1109\/SFCS.1994.365721"},{"key":"17_CR7","first-page":"307","volume":"32","author":"K. E. Batcher","year":"1968","unstructured":"K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference, pages 307\u2013314, 1968. Volume 32.","journal-title":"Proceedings of the AFIPS Spring Joint Computer Conference"},{"key":"17_CR8","unstructured":"P. Beame and F. Fich. Manuscript. 1996."},{"issue":"3","key":"17_CR9","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/65950.65958","volume":"36","author":"P. Beame","year":"1989","unstructured":"P. Beame and J. H\u00e5stad. Optimal bounds for decision problems on the CRCW PRAM. Journal of the ACM, 36(3):643\u2013670, 1989.","journal-title":"Journal of the ACM"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143\u2013154, 1979.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"17_CR11","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M. L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3):538\u2013544, 1984.","journal-title":"Journal of the ACM"},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M. L. Fredman","year":"1994","unstructured":"M. L. Fredman and D. E. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci., 47:424\u2013436, 1994.","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR13","volume-title":"Computer Organization and Design: The Hardware\/Software Interface","author":"J. L. Hennessy","year":"1994","unstructured":"J. L. Hennessy and D. A. Patterson. Computer Organization and Design: The Hardware\/Software Interface. Morgan Kaufmann Publ., San Mateo, CA, 1994."},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","volume":"28","author":"D. Kirkpatrick","year":"1984","unstructured":"D. Kirkpatrick and S. Reisch. Upper bounds for sorting integers on random access machines. Theoretical Computer Science, 28:263\u2013276, 1984.","journal-title":"Theoretical Computer Science"},{"key":"17_CR15","unstructured":"P. B. Miltersen. Personal communication."},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"P. B. Miltersen. Lower bounds for union-split-find related problems on random access machines. In Proc. 26th Ann. ACM Symp. Theory of Computing, pages 625\u2013634, 1994.","DOI":"10.1145\/195058.195415"},{"key":"17_CR17","unstructured":"W. J. Paul and J. Simon. Decision trees and random access machines. In Logic and Algorithmic: An International Symposium Held in Honour of Ernst Specker, pages 331\u2013340. L'Enseignement Math\u00e9matique, Universit\u00e9 de Gen\u00e8ve, 1982."},{"key":"17_CR18","unstructured":"R. Raman. Improved data structures for predecessor queries in integer sets, manuscript, 1995."},{"key":"17_CR19","unstructured":"M. Thorup. On RAM priority queues. In Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 1996."},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, pages 75\u201384, 1975.","DOI":"10.1109\/SFCS.1975.26"},{"issue":"3","key":"17_CR21","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80\u201382, 1977.","journal-title":"Information Processing Letters"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Syst. Theory, 10:99\u2013127, 1977.","journal-title":"Math. Syst. Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_131.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:31:52Z","timestamp":1619559112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_131","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}