{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T19:50:58Z","timestamp":1773863458089,"version":"3.50.1"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319196466","type":"print"},{"value":"9783319196473","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19647-3_9","type":"book-chapter","created":{"date-parts":[[2015,6,26]],"date-time":"2015-06-26T09:03:08Z","timestamp":1435309388000},"page":"89-103","source":"Crossref","is-referenced-by-count":4,"title":["A Linear Time Algorithm for Ordered Partition"],"prefix":"10.1007","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,27]]},"reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1006\/jcss.1998.1580","volume":"57","author":"A Andersson","year":"1998","unstructured":"Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? J. Comput. Syst. Sci. 57, 74\u201393 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Andersson, A.: Faster deterministic sorting and searching in linear space. In: Proceedings of 1996 IEEE Symposium of Foundations of Computer Science FOCS 1996, pp. 135\u2013141 (1996)","DOI":"10.1109\/SFCS.1996.548472"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-319-08404-6_3","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"D Belazzougui","year":"2014","unstructured":"Belazzougui, D., Brodal, G.S., Nielsen, J.S.: Expected linear time sorting for word size $$\\Omega $$ \u03a9 (log $$^{2}$$ 2 n loglogn). In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 26\u201337. Springer, Heidelberg (2014)"},{"issue":"4","key":"9_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1972","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1972)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jagm.1997.0873","volume":"25","author":"M Dietzfelbinger","year":"1997","unstructured":"Dietzfelbinger, M., Hagerup, T., Katajainen, J., Penttonen, M.: A reliable randomized algorithm for the closest-pair problem. J. Algorithms 25, 19\u201351 (1997)","journal-title":"J. Algorithms"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in $$O(n \\log \\log n)$$ O ( n log log n ) time and linear space. J. Algorithms 50, 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"key":"9_CR7","unstructured":"Han, Y.: Optimal randomized integer sorting for integers of word size $$\\Omega (\\log ^2 n)$$ \u03a9 ( log 2 n ) . Manuscript"},{"key":"9_CR8","unstructured":"Han, Y.: Construct a perfect hash function in time independent of the size of integers. To appear in FCS 2015"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/BFb0030847","volume-title":"Computing and Combinatorics","author":"Y Han","year":"1995","unstructured":"Han, Y., Shen, X.: Conservative algorithms for parallel and sequential integer sorting. In: Li, M., Du, D.-Z. (eds.) COCOON 1995. LNCS, vol. 959, pp. 324\u2013333. Springer, Heidelberg (1995)"},{"issue":"6","key":"9_CR10","doi-asserted-by":"publisher","first-page":"1852","DOI":"10.1137\/S0097539799352449","volume":"31","author":"Y Han","year":"2002","unstructured":"Han, Y., Shen, X.: Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs. SIAM J. Comput. 31(6), 1852\u20131878 (2002)","journal-title":"SIAM J. Comput."},{"key":"9_CR11","unstructured":"Han, Y., Thorup, M.: Integer sorting in $$O(n\\sqrt{\\log \\log n})$$ O ( n log log n ) expected time and linear space, In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 135\u2013144 (2002)"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(83)90023-3","volume":"28","author":"D Kirkpatrick","year":"1984","unstructured":"Kirkpatrick, D., Reisch, S.: Upper bounds for sorting integers on random access machines. Theor. Comput. Sci. 28, 263\u2013276 (1984)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/3-540-61680-2_51","volume-title":"Algorithms - ESA 1996","author":"R Raman","year":"1996","unstructured":"Raman, R.: Priority queues: small, monotone and trans-dichotomous. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol. 1136, pp. 121\u2013137. Springer, Heidelberg (1996)"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19647-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T21:48:29Z","timestamp":1748468909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-19647-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319196466","9783319196473"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19647-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}