Kurs:Algorithmen und Datenstrukturen/Kapitel 2/MergeSort

Merge Sort

MergeSort ist ein rekursiver Sortieralgorithmus. Die Strategie sieht wie folgt aus:

Besteht das Array aus nur einem Element, so ist es schon sortiert. Ansonsten teilen wir das Array in zwei Hälften. Jede dieser Hälften wird separat sortiert. Wir füllen das Ursprungsarray elementweise aus den zwei sortierten Hälften wieder auf.

Diese sogenannte divide and conquer Strategie kommt in der Informatik sehr häufig vor. Wenn wir ein Problem nicht direkt anpacken können oder wollen, so teilen wir es in zwei gleiche Teilprobleme auf, lösen diese separat, und basteln uns aus den zwei Teillösungen die Gesamtlösung.

Dieses Zusammenbasteln einer Gesamtlösung aus zwei Teillösungen ist für das Sortieren trivial: Wir setzen am Anfang der beiden Arrays einen Zeiger $i$ resp. $j$ und auf den Anfang des Zielarrays einen Zeiger $k$. Wir vergleichen nun die zwei Elemente bei $i$ und $j$ und setzen das kleinere davon an die Position $k$ und erhoehen sowohl $k$ als auch den Zeiger, von dem das Element kopiert wurde.

Die Sortieralgorithmen, die wir uns bis jetzt angeschaut haben, sind alle in-place Algorithmen: das sind Algorithmen, die zum Sortieren keinen zusätzlichen Speicherplatz benötigen, d.h. es werden immer nur zwei Elemente vertauscht. Dies ist bei MergeSort nicht mehr der Fall: wir benötigen ein zusätzliches Array, um die zwei sortierten Unterarrays wieder zusammenzufügen.

Programmierbeispiele

• MergeSort in Oberon
• MergeSort in Java
• MergeSort in Perl
• MergeSort in Pascal
• MergeSort in C

aus dem Wikipedia-Artikel Mergesort:

• MergeSort in Pascal
• MergeSort in PHP
• MergeSort in Ruby
• MergeSort in Python
• MergeSort in Haskell
• MergeSort in Java

Analyse

Bei der Analyse des asymptotischen Verhaltens können wir nicht mehr die Anzahl Vertauschungen zählen, da keine Elemente mehr vertauscht werden. Wir betrachten stattdessen die Anzahl Kopien, d.h. die Anzahl Male, das ein Element an einer anderen Stelle kopiert wird.

Da der Algorithmus rekursiv funktioniert, berechnen wir auch dessen Kosten rekursiv. Die Anzahl Kopien $K(n)$ für ein Unterarray der Länge $n$ berechnet sich demzufolge aus der Anzahl Kopien der zwei Unterarrays $2K(n/2)$ Plus noch die $n$ Kopien, um beide sortierte Hälften ins Zielarray zu kopieren.

$K(n)=2K\left({\frac {n}{2}}\right)+n$

Wir verankern die Rekursion für $n=2$ (unterhalb dieser Länge führen wir ja keine Rekursion mehr durch) und führen einige Schritte durch:

$K(2)$	$=$	$2$
$K(4)$	$=$	$2K(2)+4$	$=$	$8$
$K(8)$	$=$	$2K(4)+8$	$=$	$24$
$K(16)$	$=$	$2K(8)+16$	$=$	$64$
$\vdots$
$K(2^{i})$	$=$	$2K(2^{i-1})+2^{i}$	$=$	$i2^{i}$	$=$	$n\log _{2}n$ (für $n=2^{i}$)

Wir beweisen diese Annahme mit einer vollständigen Induktion. Wir prüfen also zuerst den Fall für $n=2$, denn den Fall $n=1$ behandeln wir als Ausnahme direkt.

$K(2)\quad =\quad 2\log _{2}2\quad =\quad 2\times 1\quad =\quad 2$.

Und nach dieser Überprüfung, die Induktion für alle natürlichen Werte i:

$K(2^{i+1})$	$=$	$2K(2^{i})+2^{i+1}$
	$=$	$2\left(i2^{i}\right)+2^{i+1}$
	$=$	$i2^{i+1}+2^{i+1}$
	$=$	$(i+1)2^{i+1}$.

Oder nach der Substitution: $n=2^{i}$:

$K(2n)$	$=$	$2K(n)+2n$
	$=$	$2n\log _{2}n+2n$
	$=$	$2n\left(\log _{2}n+1\right)$
	$=$	$2n\left(\log _{2}2n\right)$.

Die Anzahl Kopiervorgänge für $K(n)$ ist somit in ${\mathcal {O}}(n\log _{2}n)$.