|
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
|