Merge-Sort
"Teile und Herrsche" (Divide and conquer) ist ein algorithmisches Sortierverfahren. Eine Folge wird nicht als Ganzes bearbeitet, sondern in zwei möglichst gleich große Teilfolgen zerlegt. Diese werden solange geteilt bis die Teilfolgen praktisch nur 1 Element enthalten. Die kleinsten benachbarten Teilfolgen werden verglichen und sortiert. Die Prozedur des Zusammenfügens (merge) der sortierten Teilfolgen erzeugt die sortierte Folge.
Ein Beispiel:
Die Komplexität der Lösung nach diesem Verfahren lässt sich berechnen. T(n) sei die Anzahl der Schritte, die ein Algorithmus benötigt, eine Folge der Länge n in genau zwei gleichgroße Teile zu zerlegen. Unter der Voraussetzung, dass die benötigten Zwischenschritte bei jedem Teilen und Zusammenfügen proportional zu n sind, ergibt sich die folgende Gleichung für T mit der Konstanten c.
T(n)=2*T(n/2)+c*n und T(1)=0
Die Lösung der Gleichung T(n) lautet:
T(n)=c*n*log2(n)
