Benjamin Aram Berendsohn

Weitere Details zum Integer-Sorting-Algorithmus von Han und Thorup

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 06.12.2016

Kurzbeschreibung

Sortieren ist ein fundamentales algorithmisches Problem mit vielfältigen Anwendungsmöglichkeiten. Für die Laufzeit von vergleichsbasiertem Sortieren ist eine untere Schranke von Omega(n log n) bekannt, für das Sortieren von ganzen Zahlen (integer sorting) gilt diese Schranke allerdings nicht. Für die Word-RAM, eine Variante der RAM, die zwar Operationen im Einheitskostenmaß misst, aber eine abhängig von der Anzahl und Größe der Eingabezahlen beschränkte Registergröße hat, existieren Algorithmen, die Zahlen beliebiger Größe in o(n log n) Zeit sortieren können. In dieser Arbeit soll der Algorithmus von Han und Thorup mit einer Laufzeit von O(n sqrt(log log n)) vorgestellt werden. Dabei wird sich auf das folgende Hauptergebnis beschränkt: ein Algorithmus zum Partitionieren von n Zahlen in eine Folge von Teilmengen, sodass alle Elemente einer Teilmenge kleiner als die der folgenden Teilmenge sind und jede Teilmenge höchstens sqrt(n) Zahlen oder nur gleiche Zahlen enthält.