|
Hierbei handelt es sich um die Original-Variante (Teil 1). Sie liefert das typische Bild eines "depth first"-Algorithmus.
Eine iterative Realisierung (Variante 1.b) ist nicht möglich.
Diese Variante muß noch mit einer anderen Variante (ab 4) kombiniert werden.
| Variante | 1.a (rekursiv) |
|---|
| Typ | standard |
|---|
| Eigenschaften | rekursiv, ???, ???, parallelisierbar |
|---|
| Datenstrukturen | Felder, einfachverkettete Listen |
|---|
| Speicher | Ω(logn) | Θ(logn) | Ο(logn) |
|---|
| Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
|---|
| Laufzeit | Ω(nlogn) | Θ(nlogn) | Ο(nlogn) |
|---|
| Vergleiche | ??? | ??? | ??? |
|---|
| Vertauschungen | ??? | ??? | ??? |
|---|
mergesort(field A, int l, int r) {
if (l < r) then {
q:= (l+r) div 2;
do parallel {
mergesort(A, l, q);
mergesort(A, q+1, r);
}
merge(A, l, q, r);
}
}
merge(field A, int l, int q, int r) {
...
}
| |
Mergesort, Variante 1+5
Mergesort, Variante 1+6
|