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)
Beh.: |
![]() |
Zeige: |
![]() |
Verankerung:
![]() |
![]() |
![]() |
Induktionsschluss
Sei bis bewiesen
![]() |
![]() |
![]() |
|
Rek. | |
![]() |
|
![]() |
|
Induktionsannahme | |
![]() |
|
![]() |
|
![]() |
|
![]() |
Aber:
Mergesort benötigt zusätzlichen Platz!
Iterative Version von Mergesort (für )
l = 1; /* Länge der sortierten Teilfolgen */
k = n; /* Anzahl der sortierten Teilfolgen */
while (k > 1) {
/* alle Teilfolgen der Länge sind sortiert */
/* Sie beginnen bei für
*/
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 sind sortiert */
/* Sie beginnen bei für
*/
}
Es ergeben sich Phasen mit jeweils linearem Aufwand.
Source:
SortTest.java
JavaDoc:
SortTest.html
Applet: