Hierbei handelt es sich um die Original-Variante (Teil 2).
Eine rekursive Realisierung (Variante 4.b) ist möglich.
Variante | 4.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, out-of-place, instabil, ??? |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | nlogn | nlogn | nlogn |
Kopierungen | 2nlogn | 2nlogn | 2nlogn |
mergesort(field A, int l, int r) {
...
}
merge(field A, int l, int q, int r) {
for i:=l to q do parallel {
B[i]:= A[i];
}
for j:=q+1 to r do parallel {
B[r+q+1-j]:= A[j];
}
i:= l;
j:= r;
for k:=l to r do {
if (B[i] <= B[j]) then {
A[k]:= B[i];
i++;
} else {
A[k]:= B[j];
j--;
}
}
}
| |
Mergesort, Variante 4
|