Editing Trie (section)

=== Sorting ===
[[Lexicographic order|Lexicographic sorting]] of a set of string keys can be implemented by building a trie for the given keys and traversing the tree in [[Tree traversal#Pre-order implementation|pre-order]] fashion;<ref>{{cite web |url=https://www.cs.helsinki.fi/u/tpkarkka/opetus/12s/spa/lecture02.pdf |title=Lecture 2 |first=Juha |last=Kärkkäinen |quote="The preorder of the nodes in a trie is the same as the lexicographical order of the strings they represent assuming the children of a node are ordered by the edge labels." |publisher=[[University of Helsinki]]}}</ref> this is also a form of [[radix sort]].<ref>{{Cite web|url=https://www.ifi.uzh.ch/dam/jcr:27d15f69-2a44-40f9-8b41-6d11b5926c67/ReportKallisMScBasis.pdf|title=The Adaptive Radix Tree (Report #14-708-887)|last=Kallis|first=Rafael|date=2018|website=University of Zurich: Department of Informatics, Research Publications}}</ref> Tries are also fundamental data structures for [[burstsort]], which is notable for being the fastest string sorting algorithm as of 2007,<ref name="cachestringsort">{{cite journal | url=https://people.eng.unimelb.edu.au/jzobel/fulltext/acmjea06.pdf | doi=10.1145/1187436.1187439 | author=Ranjan Sinha and Justin Zobel and David Ring | title=Cache-Efficient String Sorting Using Copying | journal=ACM Journal of Experimental Algorithmics | volume=11 | pages=1&ndash;32 | date=Feb 2006 | s2cid=3184411 }}</ref> accomplished by its efficient use of CPU [[cache (computing)|cache]].<ref name="stringradix">{{cite book | doi=10.1007/978-3-540-89097-3_3 | author=J. Kärkkäinen and T. Rantala | chapter=Engineering Radix Sort for Strings | editor=A. Amir and A. Turpin and A. Moffat | title=String Processing and Information Retrieval, Proc. SPIRE | publisher=Springer | series=Lecture Notes in Computer Science | volume=5280 | pages=3–14 | year=2008 | isbn=978-3-540-89096-6 }}</ref>