Hierbei handelt es sich um eine alternative, verbesserte Variante. Die Idee ist einfach: Ein temporäres Indexfeld
(bidirektional) spart Speicherplatz, Kenntnisse über die Elemente und reduziert das Risiko eines Datenverlustes (da in-place).
Eine rekursive Realisierung (Variante 6.b) ist möglich.
Variante | 6.a (iterativ) |
Typ | optimiert |
Eigenschaften | iterativ, in-place, instabil, ??? |
Datenstrukturen | Felder |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | nlogn | nlogn | nlogn |
Verschiebungen | 0 | nlogn | nlogn |
mergesort(field A, int l, int r) {
...
}
merge(field A, int l, int q, int r) {
for i:= l to q do parallel {
B[0][i]:= i;
B[1][i]:= i;
}
for j:= q+1 to r do parallel {
B[0][j]:= r+q+1-j;
B[1][j]:= r+q+1-j;
}
i:= l;
j:= r;
for k:= l to r-1 do {
s:= B[0][i];
t:= B[0][j];
if (A[s] <= A[t]) then {
i++;
} else {
s:= t;
j--;
}
exchange(A[k], A[s]);
t:= B[1][k];
B[0][t]:= s;
B[1][s]:= t;
}
}
| |
Mergesort, Variante 1+6
Mergesort, Variante 2+6
|