{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:10:14Z","timestamp":1778249414259,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602163","type":"print"},{"value":"9783540447337","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0030847","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T03:51:40Z","timestamp":1133409100000},"page":"324-333","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Conservative algorithms for parallel and sequential integer sorting"],"prefix":"10.1007","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaojun","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"34_CR1","unstructured":"S. Albers and T. Hagerup. Improved parallel integer sorting without concurrent writing. Proc. The Third Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 463\u2013472."},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/BF01759076","volume":"6","author":"R. Anderson","year":"1991","unstructured":"R. Anderson and G. Miller. Deterministic parallel list ranking. Algorithmica 6: 859\u2013868(1991).","journal-title":"Algorithmica"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0890-5401(91)90031-V","volume":"94","author":"P.C.P. Bhatt","year":"1991","unstructured":"P.C.P. Bhatt, K. Diks, T. Hagerup, V.C. Prasad, T. Radzik, S. Saxena. Improved deterministic parallel integer sorting. Information and Computation\n94, 29\u201347(1991).","journal-title":"Information and Computation"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and D. E. Willard. Blasting through the information theoretic barrier with fusion trees. Proc. 1990 ACM Symp. on Theory of Computing, pp. 1\u20137(1990).","DOI":"10.1145\/100216.100217"},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0890-5401(87)90062-9","volume":"75","author":"T. Hagerup","year":"1987","unstructured":"T. Hagerup. Towards optimal parallel bucket sorting. Inform. and Comput.\n75, pp. 39\u201351(1987).","journal-title":"Inform. and Comput."},{"key":"34_CR6","volume-title":"Ph.D. Thesis","author":"Y. Han","year":"1987","unstructured":"Y. Han. Designing fast and efficient parallel algorithms. Ph.D. Thesis. Department of Computer Science, Duke University, Durham, North Carolina, 1987."},{"key":"34_CR7","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/0743-7315(89)90005-1","volume":"6","author":"Y. Han","year":"1989","unstructured":"Y. Han. Parallel algorithms for computing linked list prefix. J. of Parallel and Distributed Computing\n6 537\u2013557(1989).","journal-title":"J. of Parallel and Distributed Computing"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(90)90097-H","volume":"36","author":"T. Hagerup","year":"1990","unstructured":"T. Hagerup and H. Shen. Improved nonconservative sequential and parallel integer sorting. Infom. Process. Lett.\n36, pp. 57\u201363(1990).","journal-title":"Infom. Process. Lett."},{"key":"34_CR9","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\n28, pp. 263\u2013276(1984).","journal-title":"Theoretical Computer Science"},{"key":"34_CR10","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1109\/TC.1973.5009159","volume":"C-22","author":"P. M. Kogge","year":"1973","unstructured":"P. M. Kogge and H. S. Stone. A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Trans. Comput., Vol C-22, pp. 786\u2013792(Aug. 1973).","journal-title":"IEEE Trans. Comput."},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"R. E. Ladner and M. J. Fischer. Parallel prefix computation. J. ACM, pp. 831\u2013838(Oct. 1980).","DOI":"10.1145\/322217.322232"},{"issue":"No.7","key":"34_CR12","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1109\/TC.1978.1675167","volume":"c-27","author":"F. Preparata","year":"1978","unstructured":"F. Preparata. New parallel-sorting schemes. IEEE Transactions on Computers, Vol. c-27, No. 7, pp. 669\u2013673(July 1978).","journal-title":"IEEE Transactions on Computers"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"S. Rajasekaran and J. Reif. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM J. Comput.\n18, pp. 594\u2013607.","DOI":"10.1137\/0218041"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01178563","volume":"29","author":"S. Rajasekaran","year":"1992","unstructured":"S. Rajasekaran and S. Sen. On parallel integer sorting. Acta Informatica\n29, 1\u201315(1992).","journal-title":"Acta Informatica"},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"R. Raman. The power of collision: randomized parallel algorithms for chaining and integer sorting. Proc. 10th Conf. on Foundations of Software Technology and Theoretical Computer Science, Springer Lecture Notes in Computer Science, Vol. 472, pp. 161\u2013175.","DOI":"10.1007\/3-540-53487-3_42"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. Valiant","year":"1975","unstructured":"L. Valiant. Parallelism in comparison problems. SIAM J. Comput., 4, pp. 348\u2013355(1975).","journal-title":"SIAM J. Comput."},{"key":"34_CR17","unstructured":"R.A. Wagner and Y. Han. Parallel algorithms for bucket sorting and the data dependent prefix problem. Proc. 1986 International Conf. on Parallel Processing, pp. 924\u2013930."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0030847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T13:13:59Z","timestamp":1778246039000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0030847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602163","9783540447337"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0030847","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}