Mergesort


Der Mergesort Algorithmus ist ein Sortieralgorithmus, der nach dem Teile-und-Beherrsche-Prinzip arbeitet. Das heißt er teilt das Problem in mehrere Teilprobleme auf und löst jedes Teilproblem rekursiv. Anschließend kombiniert er diese Teillösungen miteinander um so zur Lösung des eigentlichen Problem zu gelangen.

Konkret bedeutet das für Mergesort, dass der Algorithmus die Eingabe in mehrere kleinen Listen zerlegt. Jede dieser Liste wird nun sortiert. Im Reißverschlussverfahren werden dann die kleinen Listen wieder zum großen Ganzen zusammengefügt.

Grafisches Beispiel:

Anbei ein grafischer Überblick, wie Mergesort arbeitet:
Beispiel des Mergesort Algorithmus

Pseudocode von Mergesort

Der nachfolgende Pseudocode von Mergesort stammt aus dem Buch "Algorithmen - Eine Einführung" und wurde von mir etwas um Kommentare ergänzt. Er soll noch einmal die Vorgehensweise des Algorithmus verdeutlichen und kann mit jeder Programmiersprache umgesetzt werden.

Mergesort setzt sich aus den folgenden zweil Teilen zusammen:

MERGESORT(A,p,r)

if p < r
	q = ⌊(p+r)/2⌋
	MERGESORT(A,p,q)
	MERGESORT(A,q+1,r)
	MERGE(A,p,q,r)
	

MERGE(A,p,q,r)

// n1 und n2 sind die jeweiligen Größen der Teilfelder
n1 = q-p+1
n2 = r-q

seien L[1...n1+1], R[1...n2+1] zwei neue Felder

// Fülle das neue Teilfeld L mit Daten aus Feld A
for i = 1 to n1
	L[i]=A[p+i-1]
// Fülle das neue Teilfeld R mit Daten aus Feld A
for j = 1 to n2
	R[j]=A[q+j]
L[n1 + 1] = 
R[n2 + 1] = 
i = 1 
j = 1
for k = p to r
		if L[i] ≤ R[j]
			A[k] = L[i]
			i = i+1
		else A[k] = R[j]
			j = j + 1

Eine Schleifeninvariante von Mergesort ist beispielsweise, dass zu Beginn jeder Iteration der dritten for-Schleife das Teilfeld A[p...k-1] die k-p kleinsten Elemente aus den beiden Listen L[1...n1+1] und R[1...n2+1] in sortierter Reihenfolge enthält.


Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972