Mergesort

Dësen Informatiksartikel ass eréischt just eng Skizz. Wann Dir méi iwwer dëst Theema wësst, sidd Dir häerzlech invitéiert, aus dëse puer Sätz e richtegen Artikel ze schreiwen. Wann Dir beim Schreiwen Hëllef braucht, da luusst bis an d'FAQ eran.

Mergesort ass ee séiert allgemengt Zortéierverfahren, dat 1945 vum John von Neumann virgestallt ginn ass. Et ass eng rekursiv, stabil awer net in-place Zortéiermethod, déi nom Divide and Conquer-Prinzip schafft.

Funktiounsweis

Mergesort ass eng speziell Uwennung von enger allgemenger Prozedur fir rekursiv Algorithmen.

D'Prinzip vun Divide and Counquer huet dräi Schrëtt:

1. Divide: De Problem gëtt an eng Zuel vu gläichgroussen Deelproblemer zerluecht.
2. Conquer: Deelproblemer ginn duerch Rekursioun (duerch Opruff vum selwechten Algorithmus) geléist.
3. Combine: Déi eenzel Léisunge ginn zu enger Gesamtléisung vum Originalproblem nees zesummegesat. Hei gëtt déi eigentlech Aarbecht gemaach.

Bei Mergesort bedeit dëst:

1. Divide: Mergesort spléckt een Tableau $A[1..n]$ vun $n$ Elementer, déi zortéiert solle ginn, an zwéin Deeler vun der Gréisst $n/2$ op.
2. Conquer: Déi zwéin Deeltableaue gi rekursiv mat Mergesort zortéiert.
3. Combine: Merge mëscht déi zwéin zortéiert Deeltableauen, soudatt s'eng zortéiert Sequenz erginn.

Algorithmus

De follgende Pseudocode stellt eng Implementéierung vum Algorithmus dur:

Mergesort(A,p,r)
	if p<r then
		q:= (p+r)/2
		Mergesort(A,p,q)
		Mergesort(A,q+1,r)
		Merge(A,p,q,r)
	fi
end

Prozedur Merge

Merge(A,p,q,r)
	i:= p
	j:= q+1
	k:= p
	while i<=m and j<=r do
		if A[i]<A[j] then
			B[k]:= A[i]
			i:= i+1
		else
			B[k]:= A[j]
			j:= j+1
		fi
		k:= k+1
	od

	while i<=m do
		B[k]:= A[i]
		i:= i+1
		k:= k+1
	od

	while j<=r do
		B[k]:= A[j]
		j:= j+1
		k:= k+1
	od

	// Kopéiere vum Tableau B nees an den Tableau A
	for i:=p to r do
		A[i]:= B[i]
	od
end

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990.