{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:28:46Z","timestamp":1767140926235,"version":"build-2238731810"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T00:00:00Z","timestamp":1567641600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,5]],"date-time":"2019-09-05T00:00:00Z","timestamp":1567641600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00453-019-00626-0","type":"journal-article","created":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T10:42:58Z","timestamp":1567766578000},"page":"966-978","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Sorting Real Numbers in $$O\\big (n\\sqrt{\\log n}\\big )$$ Time and Linear Space"],"prefix":"10.1007","volume":"82","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,5]]},"reference":[{"key":"626_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"626_CR2","unstructured":"Andersson, A.: Faster deterministic sorting and searching in linear space. In: Proceedings of the 1996 IEEE International Conference on Foundations of Computer Science (FOCS\u20191996), pp. 135\u2013141 (1996)"},{"key":"626_CR3","doi-asserted-by":"crossref","unstructured":"Andersson, A., Thorup, M.: Tight(er) worest-case bounds on dynamic searching and priority queues. In: Proceedings of the 2000 ACM Symposium on Theory of Computing STOC\u20192000, pp. 335\u2013342 (2000)","DOI":"10.1145\/335305.335344"},{"key":"626_CR4","doi-asserted-by":"crossref","unstructured":"Blum, L., Shub, M., Smale, M.: On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines. In: Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS\u20191988), pp. 387\u2013397 (1988)","DOI":"10.1109\/SFCS.1988.21955"},{"key":"626_CR5","volume-title":"Introduction to Algorithms","author":"TH Corman","year":"2009","unstructured":"Corman, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"626_CR6","unstructured":"Han, Y.: Integer sorting and integer related computation. Proposal submitted to NSF in 2011"},{"key":"626_CR7","unstructured":"Han, Y.: Serial and parallel sorting algorithms with applications. Proposal submitted to NSF in 2012"},{"key":"626_CR8","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)$$ time and linear space. J. Algorithms 50, 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"key":"626_CR9","doi-asserted-by":"crossref","unstructured":"Han, Y.: A linear time algorithm for ordered partition. In: Proceedings of the 2015 International Frontiers in Algorithmic Workshop (FAW\u201915), LNCS, vol. 9130, pp. 89\u2013103 (2015)","DOI":"10.1007\/978-3-319-19647-3_9"},{"key":"626_CR10","doi-asserted-by":"crossref","unstructured":"Han, Y., Shen, X.: Conservative algorithms for parallel and sequential integer sorting. In: Proceedings of the 1995 International Conference on Computing and Combinatorics. Lecture Notes in Computer Science, vol. 959, pp. 324\u2013333 (1995, August)","DOI":"10.1007\/BFb0030847"},{"key":"626_CR11","unstructured":"Han, Y., Shen, X.: Parallel integer sorting is more efficient than parallel comparison sorting on exclusive write PRAMs. In: Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999). Baltimore, pp. 419\u2013428, January 1999. Also in SIAM J. Comput. 31(6), 1852\u20131878 (2002)"},{"key":"626_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":"626_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity Theory of Real Functions. Progress in Theoretical Computer Science","author":"K Ko","year":"1991","unstructured":"Ko, K.: Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkh\u00e4user, Boston (1991)"},{"key":"626_CR14","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Dynamic integer sets with optimal rank, select, and predecessor search. Proceedings of the 2014 IEEE Symposium on Foundations of Computer Science, pp. 166\u2013175 (2014)","DOI":"10.1109\/FOCS.2014.26"},{"key":"626_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis","author":"K Weihrauch","year":"2000","unstructured":"Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)"},{"key":"626_CR16","doi-asserted-by":"crossref","unstructured":"Yap, C.K.: In praise of numerical computation. In: Albers, S., Alt, H., N\u00e4her, S. (Eds.) Efficient Algorithms. LNCS, vol. 5760, pp. 380\u2013407","DOI":"10.1007\/978-3-642-03456-5_26"}],"updated-by":[{"DOI":"10.1007\/s00453-019-00652-y","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T00:00:00Z","timestamp":1575331200000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00626-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00626-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00626-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,3]],"date-time":"2020-09-03T19:30:49Z","timestamp":1599161449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00626-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,5]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["626"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00626-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,5]]},"assertion":[{"value":"7 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2019","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original version of this article unfortunately contained an error in article title and abstract.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}