A Limit Theorem for Radix Sort and Tries with Markovian Input

Kevin Leckey, Ralph Neininger, Wojciech Szpankowski

Tries are among the most versatile and widely used data structures on words. In particular, they are used in fundamental sorting algorithms such as radix sort which we study in thi…