Mergesort

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: Schabloun:Tt 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 Schabloun:Tt zortéiert.
3. Combine: Schabloun:Tt 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.

no:Sorteringsalgoritme#Flettesortering