prev up next

Previous: Bubblesort Up: Sortieren Next: Quicksort

Mergesort

Idee (rekursiv formuliert):

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)


\begin{displaymath}
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.
\end{displaymath}

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:


prev up next
Previous: Bubblesort Up: Sortieren Next: Quicksort