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:
 Divide: De Problem gëtt an eng Zuel vu gläichgroussen Deelproblemer zerluecht.
 Conquer: Deelproblemer ginn duerch Rekursioun (duerch Opruff vum selwechten Algorithmus) geléist.
 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:
 Divide:  spléckt een Tableau  vun  Elementer, déi zortéiert solle ginn, an zwéin Deeler vun der Gréisst  op.
 Conquer: Déi zwéin Deeltableaue gi rekursiv mat  zortéiert.
 Combine:  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

Lafzäit

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

no:Sorteringsalgoritme#Flettesortering

Kategorie:Algorithmen