Mergesort

Idee (rekursiv formuliert):

• Sortiere die vordere Hälfte der Folge
• Sortiere die hintere Hälfte der Folge
• Mische die beiden sortierten Folgen zu einer sortierten Folge

Bemerkung: Diese Vorgehensweise wird Divide & Conquer (Teile und Beherrsche) genannt, da das usprüngliche Problem zunächst in unabhängige Teilprobleme zerlegt wird und danach die Teillösungen wieder zusammengeführt werden.

Die Hilfsroutine zum Mischen lautet: Source: Merge.java     JavaDoc: Merge.html    

Analyse von Mergesort (und ähnlich gelagerten Rekursionen)

$$f(n)\leq \left\{ \begin{array}{ll} c_{1} & \mbox{ f\uml {u... ...rac {n}{2})+ c_{2} \cdot n& \mbox{ sonst} \end{array} \right.$$

Beh.:	$f\in O(n \cdot \log n)$
Zeige:	$f(n)\leq (c_{1}+ c_{2})\cdot n \cdot \log n+c_1$

Verankerung:

$n=1\Rightarrow$	$f(1)\leq c _ 1$ nach Rekursion
	$f(1)\leq (c_1+c_{2})\cdot 1 \cdot \log 1+ c_1$

Induktionsschluss

Sei bis $n - 1$ bewiesen

$f(n)$	$\leq 2\cdot f(\frac{n}{2})+c_{2}\cdot n$
	$\uparrow$
	Rek.
	$\leq 2\cdot [(c_{1}+c_{2})\cdot \frac{n}{2}\cdot \log \frac{n}{2}+c_{1}]+c_{2}\cdot n$
	$\uparrow$
	Induktionsannahme
	$=2\cdot [(c_{1}+c_{2})\cdot \frac{n}{2}\cdot (\log {n}-{1})+ c_{1}]+c_{2}\cdot n$
	$=(c_{1}+c_{2})n\cdot \log n-(c_{1}+c_{2})\cdot n+2c_{1}+c_{2}\cdot n$
	$=[(c_{1}+c_{2})n \cdot \log n+c_{1}]+[c_{1}-c_{1}\cdot n]$
	$\leq (c_{1}+c_{2}) n \cdot \log n+ c_1$

Aber: Mergesort benötigt $O(n)$ zusätzlichen Platz!

Iterative Version von Mergesort (für $n=2^{k}$)

l = 1; /* Länge der sortierten Teilfolgen */
k = n; /* Anzahl der sortierten Teilfolgen */
while (k > 1) {
     /* alle Teilfolgen der Länge $l$ sind sortiert */
     /* Sie beginnen bei $l \cdot i$ für $i = 0, 1, \ldots , k - 1$ */
     Mische je zwei benachbarte Teilfolgen der Länge l
     zu einer Teilfolge der Länge 2 * l;
     l *= 2; k /= 2;
     /* Alle Teilfolgen der Länge $l$ sind sortiert */
     /* Sie beginnen bei $l \cdot i$ für $i = 0, 1, \ldots , k - 1$ */
}

Es ergeben sich $\log n$ Phasen mit jeweils linearem Aufwand.

$\Rightarrow O(n \cdot \log n)$ Source: SortTest.java     JavaDoc: SortTest.html     Applet: