{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:37:27Z","timestamp":1743082647963,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":16,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_408","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:20Z","timestamp":1461269000000},"page":"2117-2121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["String Sorting"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"356_CR19915","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal A, Vitter JS (1988) The input\/output complexity of sorting and related problems. Commun ACM 31:1116\u20131127","journal-title":"Commun ACM"},{"key":"356_CR19916","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1109\/SFCS.1994.365721","volume-title":"Proceedings of the 35th annual symposium on foundations of computer science (FOCS\u201994)","author":"A Andersson","year":"1994","unstructured":"Andersson A, Nilsson S (1994) A new efficient radix sort. In: Proceedings of the 35th annual symposium on foundations of computer science (FOCS\u201994), Santa Fe. IEEE Computer Society Press, pp\u00a0714\u2013721"},{"key":"356_CR19917","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/297096.297136","volume":"3","author":"A Andersson","year":"1998","unstructured":"Andersson A, Nilsson S (1998) Implementing radixsort. ACM J Exp Algorithmics 3:7","journal-title":"ACM J Exp Algorithmics"},{"key":"356_CR19918","first-page":"540","volume-title":"Proceedings of the 29th annual ACM symposium on theory of computing (STOC\u201997)","author":"L Arge","year":"1997","unstructured":"Arge L, Ferragina P, Grossi R, Vitter JS (1997) On sorting strings in external memory (extended abstract). In: Proceedings of the 29th annual ACM symposium on theory of computing (STOC\u201997), El Paso. ACM, pp\u00a0540\u2013548"},{"issue":"133\u2013134","key":"356_CR19919","first-page":"136","volume":"23","author":"J Bentley","year":"1998","unstructured":"Bentley J, Sedgewick R (1998) Algorithm alley: sorting strings with three-way radix quicksort. Dr Dobb\u2019s J Softw Tools 23:133\u2013134, 136\u2013138","journal-title":"Dr Dobb\u2019s J Softw Tools"},{"key":"356_CR19920","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1002\/spe.4380231105","volume":"23","author":"JL Bentley","year":"1993","unstructured":"Bentley JL, McIlroy MD (1993) Engineering a sort function. Softw Pract Exp 23:1249\u20131265","journal-title":"Softw Pract Exp"},{"key":"356_CR19921","doi-asserted-by":"crossref","unstructured":"Fagerberg R, Pagh A, Pagh R (2006) External string sorting: faster and cache-oblivious. In: Proceedings of the 23rd annual symposium on theoretical aspects of computer science (STACS\u201906), Marseille. LNCS, vol\u00a03884. Springer, pp\u00a068\u201379","DOI":"10.1007\/11672142_4"},{"key":"356_CR19922","doi-asserted-by":"crossref","unstructured":"Franceschini G, Grossi R (2004) A general technique for managing strings in comparison-driven data structures. In: Proceedings of the 31st international colloquium on automata, languages and programming (ICALP\u201904), Turku. LNCS, vol\u00a03142. Springer, pp\u00a0606\u2013617","DOI":"10.1007\/978-3-540-27836-8_52"},{"key":"356_CR19923","doi-asserted-by":"crossref","unstructured":"Franceschini G, Grossi R (2005) Optimal in-place sorting of vectors and records. In: Proceedings of the 32nd international colloquium on automata, languages and programming (ICALP\u201905), Lisbon. LNCS, vol\u00a03580. Springer, pp\u00a090\u2013102","DOI":"10.1007\/11523468_8"},{"key":"356_CR19924","unstructured":"Grossi R, Italiano GF (1999) Efficient techniques for maintaining multidimensional keys in linked data structures. In: Proceedings of the 26th international colloquium on automata, languages and programming (ICALP\u201999), Prague. LNCS, vol\u00a01644. Springer, pp\u00a0372\u2013381"},{"key":"356_CR19925","first-page":"135","volume-title":"Proceedings of the 43rd annual symposium on foundations of computer science (FOCS\u201902)","author":"Y Han","year":"2002","unstructured":"Han Y, Thorup M (2002) Integer sorting in \n                  \n                    \n                      O\n                      (\n                      n\n                      \n                        \n                          log\n                          log\n                          n\n                        \n                      \n                      )\n                    \n                  \n                  $$O(n\\sqrt{\\log \\log n})$$\n                expected time and linear space. In: Proceedings of the 43rd annual symposium on foundations of computer science (FOCS\u201902), Vancouver. IEEE Computer Society Press, pp\u00a0135\u2013144"},{"key":"356_CR19926","first-page":"5","volume":"6","author":"PM McIlroy","year":"1993","unstructured":"McIlroy PM, Bostic K, McIlroy MD (1993) Engineering radix sort. Comput Syst 6:5\u201327","journal-title":"Comput Syst"},{"key":"356_CR19927","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/0208014","volume":"8","author":"K Mehlhorn","year":"1979","unstructured":"Mehlhorn K (1979) Dynamic binary search. SIAM J Comput 8:175\u2013198","journal-title":"SIAM J Comput"},{"key":"356_CR19928","volume-title":"Algorithms in Java, Parts 1\u20134","author":"R Sedgewick","year":"2003","unstructured":"Sedgewick, R (2003) Algorithms in Java, Parts 1\u20134, 3rd edn. Addison-Wesley, Boston","edition":"3"},{"key":"356_CR19929","first-page":"360","volume-title":"Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms (SODA\u201997)","author":"R Sedgewick","year":"1997","unstructured":"Sedgewick R, Bentley J (1997) Fast algorithms for sorting and searching strings. In: Proceedings of the 8th annual ACM-SIAM symposium on discrete algorithms (SODA\u201997), New Orleans. ACM, pp\u00a0360\u2013369"},{"key":"356_CR19930","unstructured":"Sinha R, Zobel J, Ring D (2006) Cache-efficient string sorting using copying. ACM J Exp Algorithmics 11: Article No. 1.2"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T14:57:00Z","timestamp":1553093820000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_408","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}