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

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

Analyse von Mergesort (und ähnlich gelagerten Rekursionen)

f (n)

Beh.:	f O(n . log n)
Zeige:	f (n) (c1 + c2) . n . logn + c1

Verankerung:

n = 1	f (1) c1 nach Rekursion
	f (1) (c1 + c2) . 1 . log 1 + c1

Induktionsschluss

Sei bis n - 1 bewiesen

f (n)	2 . f ( ) + c2 . n
	Rek.
	2 . [(c1 + c2) . . log + c1] + c2 . n
	Induktionsannahme
	= 2 . [(c1 + c2) . . (logn - 1) + c1] + c2 . n
	= (c1 + c2)n . logn - (c1 + c2) . n + 2c1 + c2 . n
	= [(c1 + c2)n . logn + c1] + [c1 - c1 . n]
	(c1 + c2)n . logn + c1

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 ^. i für i = 0, 1,..., 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 ^. i für i = 0, 1,..., k - 1 */
}

Es ergeben sich log n Phasen mit jeweils linearem Aufwand.

O(n ^. log n) Source: SortTest.java     JavaDoc: SortTest.html     Applet: