Hierbei handelt es sich um eine alternative verbesserte Variante (Teil 1). Sie liefert das typische Bild eines "breadth first"-Algorithmus.
Diese Variante wird häufig auch als "natürliches Mergesort" bezeichnet.
Eine rekursive Realisierung (Variante 3.b) ist möglich.
Diese Variante muß noch mit einer anderen Variante (ab 4) kombiniert werden.
Variante | 3.a (iterativ) |
Typ | alternativ, optimiert |
Eigenschaften | iterativ, ???, stabil, nicht parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit | Ω(n) | Θ(nlogn) | Ο(nlogn) |
Vergleiche | ??? | ??? | ??? |
Vertauschungen | ??? | ??? | ??? |
mergesort(field A, int l, int r) {
do {
i:= l;
asc:= true;
do {
k:= i;
while (i < r) and (A[i] <= A[i+1]) do {
i++;
}
do {
i++;
} while (i < r) and (A[i] >= A[i+1]);
if (i <= r) then {
merge(A, k, i, asc);
}
asc:= not asc;
} while (i <= r);
} while (k > l);
}
merge(field A, int l, int r, bool asc) {
...
}
| |
Bitonic Mergesort, Variante 3+5
Bitonic Mergesort, Variante 3+6
|