{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T10:22:56Z","timestamp":1781518976893,"version":"3.54.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,18]],"date-time":"2015-09-18T00:00:00Z","timestamp":1442534400000},"content-version":"tdm","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":[[2017,1]]},"DOI":"10.1007\/s00453-015-0071-1","type":"journal-article","created":{"date-parts":[[2015,9,18]],"date-time":"2015-09-18T14:26:22Z","timestamp":1442586382000},"page":"235-286","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Engineering Parallel String Sorting"],"prefix":"10.1007","volume":"77","author":[{"given":"Timo","family":"Bingmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Eberle","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,9,18]]},"reference":[{"issue":"1","key":"71_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms (JDA) 2(1), 53\u201386 (2004)","journal-title":"J. Discrete Algorithms (JDA)"},{"key":"71_CR2","unstructured":"Akiba, T.: Parallel string radix sort in C++. http:\/\/github.com\/iwiwi\/parallel-string-radix-sort (2011). Git repository accessed November 2012"},{"issue":"11","key":"71_CR3","doi-asserted-by":"crossref","first-page":"1367","DOI":"10.1109\/TC.1987.5009478","volume":"100","author":"SG Akl","year":"1987","unstructured":"Akl, S.G., Santoro, N.: Optimal parallel merging and sorting without memory conflicts. IEEE Trans. Comput. 100(11), 1367\u20131369 (1987)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"71_CR4","doi-asserted-by":"crossref","first-page":"1396","DOI":"10.1137\/110836377","volume":"43","author":"A Amir","year":"2014","unstructured":"Amir, A., Franceschini, G., Grossi, R., Kopelowitz, T., Lewenstein, M., Lewenstein, N.: Managing unbounded-length keys in comparison-driven data structures with applications to online indexing. SIAM J. Comput. 43(4), 1396\u20131416 (2014)","journal-title":"SIAM J. Comput."},{"key":"71_CR5","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/297096.297136","volume":"3","author":"A Andersson","year":"1998","unstructured":"Andersson, A., Nilsson, S.: Implementing radixsort. J. Exp. Algorithmics (JEA) 3, 7 (1998)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"71_CR6","unstructured":"Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: ACM (ed.) 8th Symposium on Discrete Algorithms (SODA), pp. 360\u2013369 (1997)"},{"key":"71_CR7","doi-asserted-by":"crossref","unstructured":"Bingmann, T., Sanders, P.: Parallel string sample sort. In: 21th European Symposium on Algorithms (ESA), no. 8125 in LNCS. Springer-Verlag (2013)","DOI":"10.1007\/978-3-642-40450-4_15"},{"key":"71_CR8","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Leiserson, C.E., Maggs, B.M., Plaxton, C.G., Smith, S.J., Zagha, M.: A comparison of sorting algorithms for the connection machine CM-2. In: 3rd Symposium on Parallel Algorithms and Architectures (SPAA), pp. 3\u201316. ACM (1991)","DOI":"10.1145\/113379.113380"},{"issue":"2","key":"71_CR9","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"RP Brent","year":"1974","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions. J. ACM (JACM) 21(2), 201\u2013206 (1974)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"71_CR10","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R Cole","year":"1988","unstructured":"Cole, R.: Parallel merge sort. SIAM J. Comput. 17(4), 770\u2013785 (1988)","journal-title":"SIAM J. Comput."},{"key":"71_CR11","unstructured":"Dementiev, R., Kettner, L., Mehnert, J., Sanders, P.: Engineering a sorted list data structure for 32 bit keys. In: 6th Workshop on Algorithm Engineering & Experiments (ALENEX), pp. 142\u2013151. SIAM (2004)"},{"key":"71_CR12","unstructured":"Eberle, A.: Parallel multiway LCP-mergesort. Bachelor Thesis, Karlsruhe Institute of Technology, to appear (2014)"},{"issue":"3","key":"71_CR13","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1145\/321592.321600","volume":"17","author":"WD Frazer","year":"1970","unstructured":"Frazer, W.D., McKellar, A.C.: Samplesort: a sampling approach to minimal storage tree sorting. J. ACM (JACM) 17(3), 496\u2013507 (1970)","journal-title":"J. ACM (JACM)"},{"key":"71_CR14","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Optimal parallel string algorithms: sorting, merging and computing the minimum. In: 16th ACM Symposium on Theory of Computing (STOC), pp. 382\u2013391 (1994)","DOI":"10.1145\/195058.195202"},{"issue":"1","key":"71_CR15","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"CAR Hoare","year":"1962","unstructured":"Hoare, C.A.R.: Quicksort. Comput. J. 5(1), 10\u201316 (1962)","journal-title":"Comput. J."},{"key":"71_CR16","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.tcs.2011.12.001","volume":"426","author":"C Kent","year":"2012","unstructured":"Kent, C., Lewenstein, M., Sheinwald, D.: On demand string sorting over unbounded alphabets. Theor. Comput. Sci.nce 426, 66\u201374 (2012)","journal-title":"Theor. Comput. Sci.nce"},{"key":"71_CR17","unstructured":"Kn\u00f6pfle, S.D.: String samplesort. Bachelor Thesis, Karlsruhe Institute of Technology, in German (2012)"},{"key":"71_CR18","volume-title":"The Art of Computer Programming, Volume 3: Sorting And Searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting And Searching, 2nd edn. Addison Wesley Longman Publishing Co., Inc, Redwood (1998)","edition":"2"},{"issue":"8","key":"71_CR19","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1109\/TC.1973.5009159","volume":"100","author":"PM Kogge","year":"1973","unstructured":"Kogge, P.M., Stone, H.S.: A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Trans. Comput. 100(8), 786\u2013793 (1973)","journal-title":"IEEE Trans. Comput."},{"key":"71_CR20","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Rantala, T.: Engineering radix sort for strings. In: 16th International Conference on String Processing and Information Retrieval (SPIRE), no. 5280 in LNCS, pp. 3\u201314. Springer-Verlag (2009)","DOI":"10.1007\/978-3-540-89097-3_3"},{"issue":"1","key":"71_CR21","first-page":"5","volume":"6","author":"PM McIlroy","year":"1993","unstructured":"McIlroy, P.M., Bostic, K., McIlroy, M.D.: Engineering radix sort. Comput. Syst. 6(1), 5\u201327 (1993)","journal-title":"Comput. Syst."},{"issue":"1","key":"71_CR22","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00453-002-0993-2","volume":"35","author":"K Mehlhorn","year":"2003","unstructured":"Mehlhorn, K., Sanders, P.: Scanning multiple sequences via cache memory. Algorithmica 35(1), 75\u201393 (2003)","journal-title":"Algorithmica"},{"issue":"2","key":"71_CR23","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1093\/ietfec\/e90-a.2.457","volume":"E90\u2013A","author":"W Ng","year":"2007","unstructured":"Ng, W., Kakehi, K.: Cache efficient radix sort for string sorting. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E90\u2013A(2), 457\u2013466 (2007)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"71_CR24","doi-asserted-by":"crossref","first-page":"69","DOI":"10.2197\/ipsjdc.4.69","volume":"4","author":"W Ng","year":"2008","unstructured":"Ng, W., Kakehi, K.: Merging string sequences by longest common prefixes. IPSJ Digit. Cour. 4, 69\u201378 (2008)","journal-title":"IPSJ Digit. Cour."},{"key":"71_CR25","unstructured":"Rantala, T.: Library of string sorting algorithms in C++. http:\/\/github.com\/rantala\/string-sorting (2007). Git repository accessed November 2012"},{"key":"71_CR26","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/351827.384249","volume":"5","author":"P Sanders","year":"2000","unstructured":"Sanders, P.: Fast priority queues for cached memory. J. Exp. Algorithmics (JEA) 5, 7 (2000)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"71_CR27","doi-asserted-by":"crossref","unstructured":"Sanders, P., Winkel, S.: Super scalar sample sort. In: 12th European Symposium on Algorithms (ESA), LNCS, vol. 3221, pp. 784\u2013796. Springer-Verlag (2004)","DOI":"10.1007\/978-3-540-30140-0_69"},{"key":"71_CR28","unstructured":"Shamsundar, N.: A fast, stable implementation of mergesort for sorting text files. http:\/\/code.google.com\/p\/lcp-merge-string-sort (2009). Source downloaded November 2012"},{"key":"71_CR29","doi-asserted-by":"crossref","unstructured":"Singler, J., Sanders, P., Putze, F.: MCSTL: The multi-core standard template library. In: Euro-Par 2007 Parallel Processing, no. 4641 in LNCS, pp. 682\u2013694. Springer-Verlag (2007)","DOI":"10.1007\/978-3-540-74466-5_72"},{"key":"71_CR30","first-page":"1","volume":"15","author":"R Sinha","year":"2010","unstructured":"Sinha, R., Wirth, A.: Engineering burstsort: toward fast in-place string sorting. J. Exp. Algorithmics (JEA) 15, 1\u201324 (2010)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"71_CR31","first-page":"1","volume":"9","author":"R Sinha","year":"2004","unstructured":"Sinha, R., Zobel, J.: Cache-conscious sorting of large sets of strings with dynamic tries. J. Exp. Algorithmics (JEA) 9, 1\u201331 (2004)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"71_CR32","first-page":"1","volume":"11","author":"R Sinha","year":"2007","unstructured":"Sinha, R., Zobel, J., Ring, D.: Cache-efficient string sorting using copying. J. Exp. Algorithmics (JEA) 11, 1\u201332 (2007)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"71_CR33","doi-asserted-by":"crossref","unstructured":"Tsigas, P., Zhang, Y.: A simple, fast parallel implementation of quicksort and its performance evaluation on SUN enterprise 10000. In: 11th Euromicro Workshop on Parallel, Distributed and Network-Based Processing (PDP), pp. 372\u2013381. IEEE Computer Society (2003)","DOI":"10.1109\/EMPDP.2003.1183613"},{"key":"71_CR34","doi-asserted-by":"crossref","unstructured":"Wassenberg, J., Sanders, P.: Engineering a multi-core radix sort. In: Euro-Par 2011 Parallel Processing, no. 6853 in LNCS, pp. 160\u2013169. Springer-Verlag (2011)","DOI":"10.1007\/978-3-642-23397-5_16"},{"issue":"6","key":"71_CR35","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1137\/0216063","volume":"16","author":"MCK Yang","year":"1987","unstructured":"Yang, M.C.K., Huang, J.S., Chow, Y.C.: Optimal parallel sorting scheme by order statistics. SIAM J. Comput. 16(6), 990\u20131003 (1987)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0071-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0071-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0071-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0071-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T14:55:50Z","timestamp":1567176950000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0071-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,18]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["71"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0071-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,18]]}}}