Hierbei handelt es sich um die Original-Variante (Teil 2).
Eine rekursive Realisierung (Variante 4.b) ist möglich.
In Verbindung mit Variante 2/3 sind weitere Optimierungen möglich, indem "merge" Elemente ausschließlich in
eine Richtung (von Feld A nach Feld B oder umgekehrt) kopiert.
Variante | 4.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, out-of-place, stabil, ??? |
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 r, bool asc) {
for i:=l to r do parallel {
B[i]:= A[i];
}
if asc then {
k:= l;
c:= +1;
} else {
k:= r;
c:= -1;
}
i:= l;
j:= r;
while (i <= j) do {
if (B[i] < B[j]) or (asc and (B[i] = B[j])) then {
A[k]:= B[i];
i++;
} else {
A[k]:= B[j];
j--;
}
k:= k + c;
}
}
| |
Bitonic Mergesort, Variante 1+4
Bitonic Mergesort, Variante 2+4
|