Kevin Leckey, TU Dortmund: Radix Sort and the Markov Source Model (Oberseminar Mathematische Stochastik)
Wednesday, 24.04.2019 17:00 im Raum SRZ 117
Radix sort is a non-comparison based sorting algorithm with a wide range of applications. Although often used for integers, it can also be used for sorting words alphabetically. The algorithm splits a list of words into so-called buckets based on their first character, then continues splitting each bucket recursively based on the next character. The algorithm terminates once no bucket contains more than one word. Assigning a word to a bucket is usually called a bucket operation. The time complexity of radix sort is governed by number of these bucket operations.
Since the number of bucket operations heavily depends on the input, we will discuss some of the typical random input models and the performance of radix sort under these models. In particular, we discuss a limit theorem for the number of bucket operations as the number of words tends to infinity. This theorem is based on the so-called contraction method, an approach particularly well-suited for deriving limit theorems in random recursive structures or algorithms.
The methods presented in this talk are also applicable to several related problems. In particular the path length of digital trees, such as Tries, PATRICIA Tries, and digital search trees, can be studied in a similar manner.