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. Das Prinzip ist einfach: Es werden natürlich sortierte Folgen gesucht. Dadurch werden Vergleichsoperationen eingespart.
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, ???, ???, 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;
do {
k:= i;
while (i < r) and (A[i] <= A[i+1]) do {
i++;
}
q:= i;
do {
i++;
} while (i < r) and (A[i] <= A[i+1]);
if (i <= r) then {
merge(A, k, q, i);
}
} while (i <= r);
} while (k > l);
}
merge(field A, int l, int q, int r) {
...
}
| |
Mergesort, Variante 3+5
Mergesort, Variante 3+6
|